Suppose we have a standard deck of cards that we want to shuffle. A *perfect riffle shuffle *is defined by splitting the deck into two decks of 26 cards each and then interlacing the cards. There are two ways we can interlace the decks. The first moves the top card to the second-from-the-top spot. We call this first method an *in shuffle*. The second preserves both the top and bottom cards. We call this second method an *out shuffle*.

We can mathematically model a deck of cards by the set of integers where denotes the card’s position from the top. In a card deck, the card with position is the top card, and the card with position is the bottom card.

When we perform an out shuffle, we place a card below each card of the top half. Equivalently, we place a card above each card of the bottom half. So if a card has position , then it moves to position . If a card has position , then it moves to position

Since , for , we can represent a perfect out riffle shuffle of a card deck by the mapping

We can equivalently represent by

Since the top and bottom card of a deck are fixed in a perfect out riffle shuffle, we see that an in shuffle can be viewed as an out shuffle with deck size .

How many perfect out riffle shuffles does it take to return a deck of cards to its original order? Since the symmetric group is finite, any riffle shuffle has finite order. So we know after finitely many shuffles, the deck will return to its original order. To find the exact number of out shuffes, we only need to find the order of the element in the multiplicative group . Denote the perfect out riffle shuffle by . Indeed, for ,

To find the order of in the group , we use a simple Python script which computes until we find the minimal integer such that . For , we find that the order of is .

# Start at 1 i = 1 # Continue until we find the minimal positive integer i # such that 2^i mod 51 = 1. while ((2**i % 51) != 1): i += 1 print i

To illustrate the act of shuffling a standard deck of cards, I have written some Python code that permutes the set as defined by a perfect riffle shuffle.

def riffle_shuffle(deck, type = True): #Deck is a list of 52 distinct objects #Type is optional parameter specifying in or out shuffle; the default value is 'Out' #Split the deck into two halves using list comprehensions Deck1 = [x for x in deck if deck.index(x) < 26] Deck2 = [x for x in deck if deck.index(x) >= 26] #If the optional parameter type is True, then the shuffle is out; otherwise, it is in if type: for i in range(0,26): deck[2*i] = Deck1[i] deck[2*i+1] = Deck2[i] else: for i in range(0,26): deck[2*i] = Deck2[i] deck[2*i+1] = Deck1[i] #Return the shuffled deck return deck

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

27 | 14 | 33 | 17 | 9 | 5 | 3 | 2 |

2 | 27 | 14 | 33 | 17 | 9 | 5 | 3 |

28 | 40 | 46 | 49 | 25 | 13 | 7 | 4 |

3 | 2 | 27 | 14 | 33 | 17 | 9 | 5 |

29 | 15 | 8 | 30 | 41 | 21 | 11 | 6 |

4 | 28 | 40 | 46 | 49 | 25 | 13 | 7 |

30 | 41 | 21 | 11 | 6 | 29 | 15 | 8 |

5 | 3 | 2 | 27 | 14 | 33 | 17 | 9 |

31 | 16 | 34 | 43 | 22 | 37 | 19 | 10 |

6 | 29 | 15 | 8 | 30 | 41 | 21 | 11 |

32 | 42 | 47 | 24 | 38 | 45 | 23 | 12 |

7 | 4 | 28 | 40 | 46 | 49 | 25 | 13 |

33 | 17 | 9 | 5 | 3 | 2 | 27 | 14 |

8 | 30 | 41 | 21 | 11 | 6 | 29 | 15 |

34 | 43 | 22 | 37 | 19 | 10 | 31 | 16 |

9 | 5 | 3 | 2 | 27 | 14 | 33 | 17 |

35 | 18 | 35 | 18 | 35 | 18 | 35 | 18 |

10 | 31 | 16 | 34 | 43 | 22 | 37 | 19 |

36 | 44 | 48 | 50 | 51 | 26 | 39 | 20 |

11 | 6 | 29 | 15 | 8 | 30 | 41 | 21 |

37 | 19 | 10 | 31 | 16 | 34 | 43 | 22 |

12 | 32 | 42 | 47 | 24 | 38 | 45 | 23 |

38 | 45 | 23 | 12 | 32 | 42 | 47 | 24 |

13 | 7 | 4 | 28 | 40 | 46 | 49 | 25 |

39 | 20 | 36 | 44 | 48 | 50 | 51 | 26 |

14 | 33 | 17 | 9 | 5 | 3 | 2 | 27 |

40 | 46 | 49 | 25 | 13 | 7 | 4 | 28 |

15 | 8 | 30 | 41 | 21 | 11 | 6 | 29 |

41 | 21 | 11 | 6 | 29 | 15 | 8 | 30 |

16 | 34 | 43 | 22 | 37 | 19 | 10 | 31 |

42 | 47 | 24 | 38 | 45 | 23 | 12 | 32 |

17 | 9 | 5 | 3 | 2 | 27 | 14 | 33 |

43 | 22 | 37 | 19 | 10 | 31 | 16 | 34 |

18 | 35 | 18 | 35 | 18 | 35 | 18 | 35 |

44 | 48 | 50 | 51 | 26 | 39 | 20 | 36 |

19 | 10 | 31 | 16 | 34 | 43 | 22 | 37 |

45 | 23 | 12 | 32 | 42 | 47 | 24 | 38 |

20 | 36 | 44 | 48 | 50 | 51 | 26 | 39 |

46 | 49 | 25 | 13 | 7 | 4 | 28 | 40 |

21 | 11 | 6 | 29 | 15 | 8 | 30 | 41 |

47 | 24 | 38 | 45 | 23 | 12 | 32 | 42 |

22 | 37 | 19 | 10 | 31 | 16 | 34 | 43 |

48 | 50 | 51 | 26 | 39 | 20 | 36 | 44 |

23 | 12 | 32 | 42 | 47 | 24 | 38 | 45 |

49 | 25 | 13 | 7 | 4 | 28 | 40 | 46 |

24 | 38 | 45 | 23 | 12 | 32 | 42 | 47 |

50 | 51 | 26 | 39 | 20 | 36 | 44 | 48 |

25 | 13 | 7 | 4 | 28 | 40 | 46 | 49 |

51 | 26 | 39 | 20 | 36 | 44 | 48 | 50 |

26 | 39 | 20 | 36 | 44 | 48 | 50 | 51 |

52 | 52 | 52 | 52 | 52 | 52 | 52 | 52 |

In a deck with 2n=8 cards, for instance, we have:

0 1 2 3 4 5 6 7

After performing a out-riffle shuffle, we have:

0 4 1 5 2 6 3 7

is that right?

If so, therefore he have:

Card 0 goes to the position 2 * 0 mod 7 = 0 mod 7 = 0 , that is ok 🙂

Card 1 goes to the position 2 * 1 mod 7 = 2 mod 7 = 2 , that is ok 🙂

Card 2 goes to the position 2 * 2 mod 7 = 4 mod 7 = 4 , that is ok 🙂

Card 3 goes to the position 2 * 3 mod 7 = 6 mod 7 = 6 , that is ok 🙂

Card 4 goes to the position 2 * 4 mod 7 = 8 mod 7 = 1 , that is ok 🙂

Card 5 goes to the position 2 * 5 mod 7 = 10 mod 7 = 3 , that is ok 🙂

Card 6 goes to the position 2 * 6 mod 7 = 12 mod 7 = 5 , that is ok 🙂

Card 7 goes to the position 2 * 7 mod 7 = 14 mod 7 = 0 , CONFLICT HERE!!!

What did I do wrong?

Good catch. The error–my error, not yours–stems from the modulo 2n-1 calculation for the bottom card of the deck. I have edited the original post.

It is not so easy to see the equivalence of these two equations:

\displaystyle\pi(i):=\begin{cases}{2i\pmod{2n}} \\ {{2i+1}\pmod{2n}} \end{cases}

\displaystyle\pi(i):=\begin{cases}{2i\pmod{2n-1}} \\ {51} \end{cases}

Is there an algebraic explanation?