The Perfect Shuffle
John Szinger, 1998
I discovered some amazing mathematical patterns that emerge from the act of shuffling cards. I was idly shuffling a deck of cards when the possibility occurred to me of the "perfect" shuffle. A perfect shuffle divides the deck exacly in half, and then interleaves the two halves in strict alternation. If you could repeatedly perform such a perfect shuffle, I thought, would you come back to where you started and the deck re-align itself? Probably, I guessed. Well, then, how many shuffles would it take?
To execute a perfect shuffle with a full deck sounded difficult, so I decided to try it with a smaller deck and see how it went. As I tried different sized decks, the endeavor evolved from an idle question to a full-blown number theory project, and the result is fascinating. The answer is different for any deck size N, and it seems impossible to predict what the count will be for a given value of N before running the shuffle. The process has that magical feeling similar to finding the prime factors of numbers.
To begin, let's consider a deck of size N = 4, ordered like this:
[A,2,3,4] -- start
Now, a perfect shuffle is defined such that you divide the deck exactly in half:
[A,2], [3,4]
Then you interleave the cards from the two halves, starting with the first card from the bottom deck, yielding:
[3,A,4,2] -- after 1 shuffle
Then you iterate until you get back to the starting point.
[4,3,2,A] -- after two shuffles
Notice that the original order is reversed. This means you're halfway around. To continue:
[2,4,A,3] -- after three shuffles
And finally:
[A,2,3,4] -- success!!!
One way to track what's going on is to observe the global configuration of cards after every shuffle, as shown above. Another is to track the position of one card, such as the ace, after every shuffle. We see that the ace starts in the A position. After one shuffle it is in the 2 position, that is, the position occupied by the duece in the sorted deck. Next the ace moves to the 4 position, then the 3 position, and then back to the A position. We can express this sequence as the list [A,2,4,3]. This is the circuit the ace takes through a four card deck with repeated perfect shuffles.
Several points can be drawn from this. One is that wherever the deuce is, that's where the ace will be after the next shuffle. Also, for any card is in the front half of the deck, its position will be doubled after the shuffle. For any card in the bottom half of the deck, its position with respect to the end of the deck will be doubled. So the shuffling function is symmetrical about the center of the deck.
At this point I address some degenerate cases. Firstly, I could have just as easily defined a perfect shuffle to begin the interleave with the first card from the top half of the deck. The above example would then play out as:
[A,2,3,4] -- start
[A,3,2,4] -- one
[A,2,3,4] -- two; done.
As you can see, the first and last card never move, and the general case for the new postion P of a card can be calculated as (2 * P) - 1 from whichever end of the deck the card is closer to, so this is equivalent to doing the shuffle defined above with a deck of size (N - 2). This variaion is known by card-playing mathematicians as an Out Shuffle, while the method defined earlier is called an In Shuffle. Secondly, for the case of a deck with an odd number of cards the last card never moves, and it is equivalent to a deck of size (N - 1).
Now to return to my original question: "How many shuffles will it take to come back to the starting point?" A little logic led me to assume that it can never be more shuffles than the size of the deck. In that case, every card will visit every position exactly once in a systematic fashion. But can there be cases where the number of shuffles needed is less than the deck size?
It turns out the answer is yes! You can in fact have fewer shuffles than cards. Consider a deck of size N = 6:
[A,2,3,4,5,6] -- start
[4,A,5,2,6,3] -- one
[2,4,6,A,3,5] -- two
[A,2,3,4,5,6] -- three; done.
Whoa! Only three shuffles. What's going on here?
Well, if we track the ace, we see that it only visits half of the positions in the deck, so [A,2,4] defines a complete circuit around the deck. We can see by looking at the remaining cards that there is a second circuit: [6,5,3]. These two circuits are complimentary, that is, they can be aligned so that each element is correlated with it's compliment in the opposite list. The compliment of an element is defined such that the sum of an element and its compliment equals the size of the deck plus one. So A + 6 = 7, 2 + 5 = 7, and 3 + 4 = 7. The two circuits taken together form a compliment pair.
Moving on. If we shuffle a deck of size N = 8, we get:
[A,2,3,4,5,6,7,8] -- start
[5,A,6,2,7,3,8,4] -- one
[7,5,3,A,8,6,4,2] -- two
[8,7,6,5,4,3,2,A] -- three; reversed - halfway!!!
[4,8,3,7,2,6,A,5] -- four
[2,4,6,8,A,3,5,7] -- five
[A,2,3,4,5,6,7,8] -- six; done.
This is pretty weird. It takes six shuffles for a deck of 8. Six is not a factor of 8. What's going on? Well, if we trace the ace, we see that it goes [A,2,4,8,7,5]. It skips 3 and 6 altogether. 3 and 6 keep trading places, forming a smaller subgroup of size 2. I call this kind of a group a standing wave, since it uses all the multiples of a particluar number (in this case 3) in the deck. It divides the deck into a number of equally sized smaller groups. [A,2], [4,5] and [7,8]. The standing wave and the main group do not mutually interact. However, 2 is a factor of 6, so the standing wave cycles three times in the period of the major circuit, and so the period of the deck as whole is 6 shuffles.
We now know that perfectly suffled decks can form a single chain, pairs of complinetary chains, or non-complimentary chains of unequal size. What other configurations might there be? Is there any way to predict the number of shuffles needed as a function of the size of the deck? Is there any way to predicit the presense of complmentary pairs of chains, or of standing waves, on the basis of the size of the deck? Many fascinating qestions.
To try to answer these questions, I ran every size deck up to N = 52. There is some pattern that emerges, but it is really strange, and not altogether predictable. There is no simple linear relationship between the size of the deck and the number of shuffles, and the patterns get more complicated as the decks get larger. There is no simple formula to predict the number of seperate circuits that will appear, or what thier sizes are, or how they relate. Sometimes many factors fall out, and often the period of a deck is not a factor of the deck size. Sometimes larger decks reflect and amplify patterns found in smaller sized decks.
In addition to the compliment pairs and standing waves already illustrated, I have found myriad series of cards or pairs of sries that represent other special relationships. These include standing-wave compliment pairs, where each of the two threads is a semi-standing wave. There are also near-standing waves which, when combined with a lower frequency standing wave, fill out all the multiples of a lower number. (For example, all threes in a sequence except the nines or fifteens might constitute a near standing wave.) Another, relatively rare occuence is a prime, which means that the number of shuffles is equal to the size of the deck, and the cards go around in a single long series. I do not yet know if it is feasable to construct a complete taxonomy, or if new kinds of series will continue to appear with larger and larger decks.
Another unanswered question is whether there can be a deck where the number of shuffles required is greater than the size of the deck. Although I have not yet found and example, niether have I ruled out a case where two or more factors might phase becuase they're non-interger multiples of one another, thus causing a period greater than the number of cards.
To me the phenomena of these emergent patterns evoke the richness of the prime factorization of numbers, or electron valences and shells, or musical harmonic overtones, or the geometry of Penrose tiles, or any number of other quasi-numeric natural phenomena. For the perfect shuffle, every number has a unique and interesting set of properties that are a manifestation of its unique numeric nature.
For the whole story refer to the chart below. For each group listed, the first number is the size of the deck, that is the number of cards in the deck. The next number is the number of perfect shuffles needed before the deck gets back to its starting configuration. The lists of numbers for each group are the paths the cards take thru the deck as it is shuffled. If there is a space halfway thru a list of numbers, it means that the list is symmetrical about the center of the deck and is therefore its own compliment. The number (card) after the space is complimentary to the first number in the list, the second number after the space to the seconed number, and so on. If there is not a space in the middle of the list that means that the list is half of a compliment pair.
So without further ado, the data:
2 : 2 [A, 2]
4 : 4 [A,2, 4,3]
6 : 3 [A,2,4]
3 [6,5,3] -- compliment pair
8 : 6 [A,2,4, 8,7,5]
2 [3, 6] -- standing wave
10 : 10 [A,2,4,8,5, 10,9,7,3,6]
12 : 12 [A,2,4,8,3,6, 12,11,9,5,10,7]
14 : 4 [A,2,4,8]
4 [14,13,11,7] -- compliment pair
4 [3,6, 12,9] -- standing wave
2 [5, 10] -- standing wave
16 : 8 [A,2,4,8, 16,15,13,9]
8 [3,6,12,7, 14,11,5,10] -- non-compliments
18 : 18 [A,2,4,8,16,13,7,14,9,
18,17,15,11,3,6,12,5,10]
20 : 6 [A,2,4,8,16,11]
6 [20,19,17,13,5,8] -- compliment pair
3 [3,6,12]
3 [18,15,9] -- comp pair, semi-s.w.
2 [7, 14] -- standing wave
22 : 11 [A,2,4,8,16,9,18,13,3,6,12]
11 [22,21,19,15,7,14,5,10,20,17,11] -- compliment pair
24 : 20 [A,2,4,8,16,7,14,3,6,12,
24,23,21,17,9,18,11,22,9,13]
4 [5,10, 20,15] -- standing wave
26 : 18 [A,2,4,8,16,5,10,20,13
26,25,23,19,11,22,17,7,14]
6 [3,6,12, 24,12,15] -- near-standing wave
2 [9, 18] -- standing wave
28 : 28 [A,2,4,8,16,3,6,12,24,19,9,18,7,14
28,27,15,21,13,26,23,17,5,10,20,11,22,15]
30 : 5 [A,2,4,8,16]
5 [30,29,27,23,15] -- compliment pair
5 [3,6,12,24,17]
5 [28,25,19,7,14] -- compliment pair
5 [5,10,20,9,18]
5 [26,21,11,22,13] -- compliment pair
32 : 10 [A,2,4,8,16, 32,31,29,25,17]
10 [3,6,12,24,15, 30,27,21,9,18] -- standing wave
10 [5,10,20,7,14, 28,23,13,26,19]
2 [11, 22] -- standing wave
34 : 12 [A,2,4,8,16,32,29,23,11,22,9,18]
12 [34,33,31,27,19,3,6,12,24,13,26,17] -- compliment pair
3 [5,10,20]
3 [30,25,15] -- comp pair, semi-s.w.
4 [7,14,28,21] -- standing wave
36 : 36 [A,2,4,8,16,32,27,17,34,31,25,13,
26,15,30,23,9,18, 36,35,33,29,21,5,
10,20,3,6,12,24,11,22,7,14,28,19]
38 : 12 [A,2,4,8,16,32,25,11,22,5,10,20]
12 [38,37,35,31,23,7,14,28,17,34,29,19] -- compliment pair
12 [3,6,12,24,9,18, 36,33,27,15,30,21] -- standing wave
2 [13, 26] -- standing wave
40 : 20 [A,2,4,8,16,32,23,5,10,20
40,39,37,33,25,9,18,36,31,21]
20 [3,6,12,24,7,14,28,15,30,19
38,35,29,17,34,27,13,26,11,22] -- non-compliments
42 : 14 [A,2,4,8,16,32,21, 42,41,39,35,27,11,22]
14 [3,6,12,24,5,10,20, 40,37,31,19,38,33,23]
14 [7,14,28,13,26,9,18, 36,29,15,30,17,34,25]
44 : 12 [A,2,4,8,16,32,19,38,31,17,34,23]
12 [44,43,41,37,29,13,26,7,14,28,11,22] -- compliment pair
4 [3,6,12,24]
4 [42,39,33,21] -- compliment pair
6 [5,10,20, 40,35,25] -- near-standing wave
4 [9,18, 36,27] -- standing wave
2 [15, 30] -- standing wave
46 : 23 [A,2,4,816,32,17,34,21,42,37,27
7,14,28,9,18,36,25,3,6,12,24]
23 [46,45,43,39,31,15,30,13,26,5,10,20
40,33,19,38,29,11,22,44,41,35,23] -- compliment pair
48 : 21 [A,2,4,8,16,32,15,30,11,22,44
39,29,9,18,36,23,46,43,37,25]
21 [48,47,45,41,33,17,34,19,38,27,5,
10,20,40,31,13,26,3,6,12,24] -- compliment pair
3 [7,14,28]
3 [42,35,21] -- comp pair, semi-sw
50 : 8 [A,2,4,8,16,32,13,26]
8 [50,49,47,43,35,19,38,25] -- compliment pair
8 [3,6,12,24, 48,45,39,27]
8 [5,10,20,40,29,7,14,28]
8 [46,41,31,11,22,44,37,23] -- compliment pair
8 [9,18,36,21, 42,33,15,30]
2 [17, 34] -- standing wave
52 : 52 [A,2,4,8,16,32,11,22,44,35,17,34,15,
30,7,14,28,3,6,12,24,48,43,33,13,26,
52,51,49,45,37,21,42,31,9,18,36,19,38,
23,46,39,25,50,47,41,29,5,10,20,40,27]
