Perfect Riffle Shuffle

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 2n cards by the set of integers \left\{0,\ldots,2n-1\right\} where i denotes the card’s position from the top. In a 52 card deck, the card with position i=0 is the top card, and the card with position i=51 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 i\in\left\{0,\ldots,n-1\right\}, then it moves to position 2i. If a card has position i\in\left\{n,\ldots,2n-1\right\}, then it moves to position

\displaystyle(i-n)+(i-n+1)=2(i-n)+1=2i+1\pmod{2n}

Since 2i<2n-1, for i\left\{0,\ldots,n-1\right\}, we can represent a perfect out riffle shuffle \pi of a 2n card deck by the mapping

\displaystyle\pi(i):=\begin{cases}{2i\pmod{2n}} & {0\leq i\leq 25}\\ {{2i+1}\pmod{2n}} & {26\leq i\leq 51}\end{cases}

We can equivalently represent \pi by

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

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 2n+2=2(n+1).

How many perfect out riffle shuffles does it take to return a deck of cards to its original order? Since the symmetric group S_{52} 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 e of the element 2 in the multiplicative group \mathbb{Z}_{51}^{*}. Denote the perfect out riffle shuffle by \sigma. Indeed,  for i\left\{0,\ldots,2n-1\right\}

\displaystyle\sigma^{k}(i)=2^{k}i\pmod{2n-1}\begin{cases}{=i,} & {k=e}\\{\neq i,} & {k<e}\end{cases}

To find the order of 2 in the group \mathbb{Z}_{2n-1}, we use a simple Python script which computes 2^{i}\pmod{2n-1} until we find the minimal integer i such that 2^{i}=1\pmod{(2n-1)}. For n=52, we find that the order of 2 \pmod{(2n-1)} is 8.

# 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

\begin{array}{l}\sigma(2)=3\\ \sigma^{2}(2)=\sigma(3)=5\\ \sigma^{3}(2)=\sigma(5)=9\\ \sigma^{4}(2)=\sigma(9)=17\\ \sigma^{5}(2)=\sigma(17)=33\\ \sigma^{6}(2)=\sigma(33)=14\\ \sigma^{7}(2)=\sigma(14)=27\\ \sigma^{8}(2)=\sigma(27)=2\end{array}

To illustrate the act of shuffling a standard deck of cards, I have written some Python code that permutes the set \left\{1,\ldots,52\right\} 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
Advertisements
This entry was posted in math.CO, math.GR, Problem Solving, Progamming, Python and tagged , , . Bookmark the permalink.

3 Responses to Perfect Riffle Shuffle

  1. Luiz says:

    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?

    • Matt R. says:

      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.

  2. Tiago says:

    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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s