## Perfect Shuffle

### March 13, 2020

A perfect shuffle, also known as a faro shuffle, splits a deck of cards into equal halves (there must be an even number of cards), then perfectly interleaves them. Eventually a series of perfect shuffles returns a deck to its original order. For instance, with a deck of 8 cards named (1 2 3 4 5 6 7 8), the first shuffle rearranges the cards to (1 5 2 6 3 7 4 8), the second shuffle rearranges the cards to (1 3 5 7 2 4 6 8), and the third shuffle restores the original order (1 2 3 4 5 6 7 8).

Your task is to write a program that performs a perfect shuffle and use it to determine how many perfect shuffles are required to return an n-card deck to its original order; how many perfect shuffles are required for a standard 52-card deck? When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 15 Responses to “Perfect Shuffle”

1. Zack said

Cool drill. Here is my take on it using Julia: https://pastebin.com/ppSpZ5BH

For a 52 card deck, it takes just n = 8 perfect shuffles, while for a 54 card one (one which includes 2 jokers) it takes many more.

Have a nice weekend and stay healthy!

2. Paul said

In Python.

```from itertools import chain

def pshuffle(seq):
half = len(seq) // 2
return list(chain.from_iterable(zip(seq[:half], seq[half:])))

for N in (8, 24, 52, 100, 1020, 1024, 10000):
seq = orig = list(range(N))
for i in range(100000):
seq = pshuffle(seq)
if seq == orig:
print(i+1, end=", ")
break

# -> 3, 11, 8, 30, 1018, 10, 300,
```
3. chaw said

Here is a simple solution in R7RS Scheme and a few popular helpers.
It includes a formulaic method for computing the cycle-length in

``` (import (scheme base) (scheme write) (only (srfi 1) fold-right split-at cons* iota) (only (srfi 8) receive) (only (org eip10 okmij myenv) assert)) (define (perfect-out-shuffle items) (assert (even? (length items))) (receive (top bot) (split-at items (quotient (length items) 2)) (fold-right (lambda (top-item bot-item rslt) (cons* top-item bot-item rslt)) '() top bot))) (write (perfect-out-shuffle (iota 8 1))) (newline) (define (iterate-perfect-out-shuffles items limit show?) (let loop ((i 0) (shuf items)) (and (< i limit) (let ((shuf (perfect-out-shuffle shuf))) (when show? (write shuf) (newline)) (or (equal? shuf items) (loop (+ i 1) shuf)))))) (write (iterate-perfect-out-shuffles (iota 8 1) 10 #t)) (newline) (define (perfect-out-shuffle-cycle-length num-items) (assert (> num-items 1) (even? num-items)) (if (= 2 num-items) 1 (let ((m (- num-items 1))) (let loop ((k 1) (e 2)) (if (= 1 e) k (loop (+ k 1) (modulo (* 2 e) m))))))) (write (map perfect-out-shuffle-cycle-length (iota 100 2 2))) (newline) (write (perfect-out-shuffle-cycle-length #e1e10)) (newline) ```

Output:

``` (1 5 2 6 3 7 4 8) (1 5 2 6 3 7 4 8) (1 3 5 7 2 4 6 8) (1 2 3 4 5 6 7 8) #t (1 2 4 3 6 10 12 4 8 18 6 11 20 18 28 5 10 12 36 12 20 14 12 23 21 8 52 20 18 58 60 6 12 66 22 35 9 20 30 39 54 82 8 28 11 12 10 36 48 30 100 51 12 106 36 36 28 44 12 24 110 20 100 7 14 130 18 36 68 138 46 60 28 42 148 15 24 20 52 52 33 162 20 83 156 18 172 60 58 178 180 60 36 40 18 95 96 12 196 99) 54540 ```

4. BW25 said

Looking at the pattern of numbers, it seems it is sometimes possible to calculate the number of perfect shuffles with an equation instead of actually doing the perfect shuffles.

For an even number N and N-1, they will both have the same answer.
E.g. 52 and 51 both take 8 perfect shuffles

I’ve also noticed for any number that is 2^n, the number of perfect shuffles is n.
E.g. 8 = 2^3, n=3, so the number of perfect shuffles is 3.

For any number that is (2^n) + 2 or 2^n + 1, the answer is 2n.
E.g. 10 = (2^3)+2, n = 3. The answer is 2n = 6.
Also: 9 = (2^3)+1, n = 3. The answer is 2n = 6.

Unfortunately, I can’t figure out the pattern beyond that, but in these special cases, the number of perfect shuffles can be found in O(1) time.
If there is an equation to describe the entire pattern, perhaps all cases could be solved in O(1) time.

Code:
import numpy as np
import math

#In some cases, we do not need to actually perform the perfect shuffle: we can determine the answer with simple math
def checkSpecialCases(arr):
#An even number N will have the same solution as N-1
#Add 1 to odd numbers to make checks easier
N = len(arr) + len(arr)%2

``````#If a number is 2^x, the solution is x
calc = math.log2(N)
if calc % 1 == 0:
return int(calc)

#If a number is (2^x)+2, the solution is 2x
calc = math.log2(N-2)
if calc % 1 == 0:
return int(calc*2)

#If none of these cases are met, we have no choice but to do the perfect shuffle
return perfectShuffle(arr)
``````

def perfectShuffle(arr):
orig = np.copy(arr)

``````n = 0   #Count the number of perfect shuffles
while True:
#Copy array
arr2 = np.copy(arr)

#Place upper half of array into position
for i in range(math.ceil((len(arr)/2))):
arr[i*2] = arr2[i]
#Place lower half of array into position
for i in range(len(arr)//2):
arr[(i*2)+1] = arr2[math.ceil(len(arr)/2)+i]

n+=1    #Increase shuffle counter
#print(arr)

if np.array_equal(orig,arr):    #If the array matches the unshuffled array, we are finished.
break
return n
``````

if name == ‘main‘:
for i in range(2,9):
arr = np.arange(1,i+1)
print(str(i) + ‘ : ‘ + str(checkSpecialCases(arr)))

Output:
2 : 1
3 : 2
4 : 2
5 : 4
6 : 4
7 : 3
8 : 3

5. mclrhn@vfemail.net said

Quoting Programming Praxis :

Further;If the aim of shuffling is to make the card order unpredicatable or at least difficuld to predict; how many “faro-shuffles” of a 52-card stack is ideal ?

> programmingpraxis posted: “A perfect shuffle, also known as a faro > shuffle, splits a deck of cards into equal halves (there must be an > even number of cards), then perfectly interleaves them. Eventually a > series of perfect shuffles returns a deck to its original order. For > instance,” > > > T

6. Daniel said

Here’s a solution in C.

```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void shuffle(int* array, int n) {
int* shuffled = malloc(sizeof(int) * n);
int half = n / 2;
for (int i = 0; i < half; ++i) {
shuffled[i * 2] = array[i];
}
for (int i = half; i < n; ++i) {
shuffled[(i - half) * 2 + 1] = array[i];
}
memcpy(array, shuffled, sizeof(int) * n);
free(shuffled);
}

int main(int argc, char* argv[]) {
assert(argc == 2);
int n = atoi(argv[1]);
assert(n % 2 == 0);
int* array = malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
array[i] = i;
}
int count = 0;
while (1) {
shuffle(array, n);
++count;
for (int i = 0; i < n; ++i) {
if (array[i] != i) goto end_outer;
}
break;
end_outer: ;
}
printf("%d\n", count);
free(array);
return EXIT_SUCCESS;
}
```

Example:

```\$ for i in `seq 2 2 20`; do ./a.out \$i; done
1
2
4
3
6
10
12
4
8
18
```

As indicated on Wikipedia, this matches sequence A002326 on OEIS.

7. Globules said

```{-# LANGUAGE LambdaCase #-}

import Data.Maybe    (listToMaybe)
import GHC.Natural   (Natural, powModNatural)
import Text.Printf   (printf)

-- The type of faro shuffle.
data Shuffle = In  -- orig. top card to 2nd, bottom card to penultimate
| Out -- orig. top card to top, bottom card to bottom
deriving (Show)

-- The number of shuffles, of type s, required to restore an n card deck to its
-- original order.
numShuffles :: Shuffle -> Natural -> Maybe Natural
numShuffles s n | odd n     = Nothing
| otherwise = go (modulusFrom s n)
where modulusFrom = \case In -> succ; Out -> pred
go m = listToMaybe [e | e <- [1..], let p = powModNatural 2 e m, p == 1]

--------------------------------------------------------------------------------

test :: [(Shuffle, Natural)] -> IO ()
test sns = do
printf "Deck Size  Shuffle Type  Num Shuffles\n"
printf "---------  ------------  ------------\n"
forM_ sns \$ \(s, n) -> do
let shufs = maybe "-" show (numShuffles s n)
printf "%5d      %7s       %6s\n" n (show s) shufs

main :: IO ()
main = test [( In,     7), (Out,     7),
( In,     8), (Out,     8),
( In,    52), (Out,    52),
( In,    64), (Out,    64),
( In, 87654), (Out, 87654)]
```
```\$ ./faro
Deck Size  Shuffle Type  Num Shuffles
---------  ------------  ------------
7           In            -
7          Out            -
8           In            6
8          Out            3
52           In           52
52          Out            8
64           In           12
64          Out            6
87654           In         8556
87654          Out         6732
```
8. matthew said

I had fun with this one:

```# Cut pack into two halves, deal alternately from each
# half. An outshuffle starts from the half with the original
# top card, an inshuffle starts from the other half (so the
# top card always stays the same after an outshuffle). The
# procedure makes sense for both odd and even numbers of cards.

# The next() function describes effect of the shuffle:
# type is outshuffle = 0, inshuffle = 1
def next(i,n,type):
# A card originally at index 'i' goes to index 'next(i,n,t)'
# Need special case for last element of an even outshuffle
if n%2 == 0 and type == 0 and i == n-1: return i
if n%2 == 0 and type == 0: return (2*i) % (n-1)
if n%2 == 1 and type == 0: return (2*i) % n
if n%2 == 0 and type == 1: return (2*i+1) % (n+1)
if n%2 == 1 and type == 1: return (2*i+1) % n
assert False

print([next(i,10,0) for i in range(10)])
print([next(i,10,1) for i in range(10)])
print([next(i,11,0) for i in range(11)])
print([next(i,11,1) for i in range(11)])
# [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
# [1, 3, 5, 7, 9, 0, 2, 4, 6, 8]
# [0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
# [1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10]

# 'shuffle()' constructs the entire permutation, both
# as an array map and as a set of cycles.
#
# The length of the longest cycle is the number of shuffles
# needed to restore the original pack order.

def shuffle(n, type = 0):
# Go through 0..n-1, finding the next index, until a cycle is
# found. Record the cycle and move on to next unhandled index.
a = [-1]*n
cycles = []
for i in range(n):
c = []
while a[i] < 0:
# Add i to the current cycle
c += [i]
# and find the next index.
j = next(i,n,type)
a[i],i = j,j
# Collect non-empty cycles
if len(c) > 0: cycles.append(c)
return (a,cycles)

# inshuffle length 2n is like outshuffle length 2n+2 (imagine discarding both
# end cards), and both are like inshuffle and outshuffles of length 2n+1 and
# all four shuffles have similar cycle structure:
print(shuffle(20,1)[1])
print(shuffle(21,1)[1])
print(shuffle(21,0)[1])
print(shuffle(22,0)[1])
#      [[0, 1, 3, 7, 15, 10], [2, 5, 11], [4,  9, 19, 18, 16, 12], [6, 13], [8, 17, 14]]
#      [[0, 1, 3, 7, 15, 10], [2, 5, 11], [4,  9, 19, 18, 16, 12], [6, 13], [8, 17, 14], [20]]
# [[0], [1, 2, 4, 8, 16, 11], [3, 6, 12], [5, 10, 20, 19, 17, 13], [7, 14], [9, 18, 15]]
# [[0], [1, 2, 4, 8, 16, 11], [3, 6, 12], [5, 10, 20, 19, 17, 13], [7, 14], [9, 18, 15], [21]]

# Here, the longest cycle is 6 and this is how many shuffles are needed
# to restore the original pack order.

# The simplest form is the odd outshuffle, where index i goes to 2*i%n:
for n in range(3,22,2): print(n,[len(c) for c in shuffle(n,0)[1]])
# 3 [1, 2]
# 5 [1, 4]
# 7 [1, 3, 3]
# 9 [1, 6, 2]
# 11 [1, 10]
# 13 [1, 12]
# 15 [1, 4, 4, 2, 4]
# 17 [1, 8, 8]
# 19 [1, 18]
# 21 [1, 6, 3, 6, 2, 3]

# and we can see that the smallest k > 0 with 2**k%n == 1 will be the
# longest cycle (the cycle beginning 1 will be of this length) and in
# fact we have: 2**4%15 = 16%15 = 1; 2**6%21 == 64%21 == 1 etc.

# In general, for k outshuffles of n items, index i moves to:
def outshuffle(n,k,i):
if n%2 == 0 and i == n-1: return n-1 # Special case
m = n-1 if n%2 == 0 else n
return 2**k*i%m

# and for k inshuffles of n items, index i moves to:
def inshuffle(n,k,i):
m = n+1 if n%2 == 0 else n
return (2**k*(i+1)-1)%m

print ([inshuffle(8,1,i) for i in range(8)])
print ([inshuffle(9,1,i) for i in range(9)])
print ([outshuffle(9,1,i) for i in range(9)])
print ([outshuffle(10,1,i) for i in range(10)])
# [1, 3, 5, 7, 0, 2, 4, 6]
# [1, 3, 5, 7, 0, 2, 4, 6, 8]
# [0, 2, 4, 6, 8, 1, 3, 5, 7]
# [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]

# and the longest cycle here is 6, so:
print ([inshuffle(8,6,i) for i in range(8)])
print ([inshuffle(9,6,i) for i in range(9)])
print ([outshuffle(9,6,i) for i in range(9)])
print ([outshuffle(10,6,i) for i in range(10)])
# [0, 1, 2, 3, 4, 5, 6, 7]
# [0, 1, 2, 3, 4, 5, 6, 7, 8]
# [0, 1, 2, 3, 4, 5, 6, 7, 8]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for k in range(7): print ([outshuffle(9,k,i) for i in range(9)])
# [0, 1, 2, 3, 4, 5, 6, 7, 8]
# [0, 2, 4, 6, 8, 1, 3, 5, 7]
# [0, 4, 8, 3, 7, 2, 6, 1, 5]
# [0, 8, 7, 6, 5, 4, 3, 2, 1]
# [0, 7, 5, 3, 1, 8, 6, 4, 2]
# [0, 5, 1, 6, 2, 7, 3, 8, 4]
# [0, 1, 2, 3, 4, 5, 6, 7, 8]

# Finally, for a full 52-card pack:
for c in shuffle(52,0)[1]: print(c)
# [0]
# [1, 2, 4, 8, 16, 32, 13, 26]
# [3, 6, 12, 24, 48, 45, 39, 27]
# [5, 10, 20, 40, 29, 7, 14, 28]
# [9, 18, 36, 21, 42, 33, 15, 30]
# [11, 22, 44, 37, 23, 46, 41, 31]
# [17, 34]
# [19, 38, 25, 50, 49, 47, 43, 35]
# [51]

# The longest cycle is 8 and we have:
print([outshuffle(52,8,i) for i in range(52)] == list(range(52)))
# True
```
9. Steve said

Klong version

```
shuffle::{[d n n1 n2 n3]; d::x; n::_(#d)%2; n1::n#d; n2::(-n)#d; n{n3::(*n1),*n2; n1::1_n1; n2::1_n2; x,n3}:*[]}

shuffle(1+!20)
[1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20]

shuffle(shuffle(1+!20))
[1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19 5 10 15 20]

nshuffle::{[cnt d f]; d::x; cnt::f::0; {x; ~f}{[s]; cnt::cnt+1; f::(#d)=+/d=s::shuffle(x); s}:~d; cnt}

{.p((\$x)," --> ",\$nshuffle(1+!x))}'2*1+!26;:ok
2 --> 1
4 --> 2
6 --> 4
8 --> 3
10 --> 6
12 --> 10
14 --> 12
16 --> 4
18 --> 8
20 --> 18
22 --> 6
24 --> 11
26 --> 20
28 --> 18
30 --> 28
32 --> 5
34 --> 10
36 --> 12
38 --> 36
40 --> 12
42 --> 20
44 --> 14
46 --> 12
48 --> 23
50 --> 21
52 --> 8
:ok

```
10. Steve said

Klong version

```
shuffle::{[d n n1 n2 n3]; d::x; n::_(#d)%2; n1::n#d; n2::(-n)#d; n{n3::(*n1),*n2; n1::1_n1; n2::1_n2; x,n3}:*[]}

shuffle(1+!20)
[1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20]

shuffle(shuffle(1+!20))
[1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19 5 10 15 20]

nshuffle::{[cnt d f]; d::x; cnt::f::0; {x; ~f}{[s]; cnt::cnt+1; f::(#d)=+/d=s::shuffle(x); s}:~d; cnt}

{.p((\$x)," --> ",\$nshuffle(1+!x))}'2*1+!26;:done
2 --> 1
4 --> 2
6 --> 4
8 --> 3
10 --> 6
12 --> 10
14 --> 12
16 --> 4
18 --> 8
20 --> 18
22 --> 6
24 --> 11
26 --> 20
28 --> 18
30 --> 28
32 --> 5
34 --> 10
36 --> 12
38 --> 36
40 --> 12
42 --> 20
44 --> 14
46 --> 12
48 --> 23
50 --> 21
52 --> 8
:done

```
11. Sam Claflin said

Sorry for lack of formatting, new to the site. This is a vanilla Python solution; I was stumped for a bit but figured it out pretty quickly after drawing out a couple of cards and seeing how they moved.

Number of shuffles for 52 cards: 8

for i in range(2, 14, 2):
# Initialize deck size
deck_size = i
if deck_size % 2 != 0:
msg = “Deck size must be even”
raise ValueError(msg)

``````# Create deck function
def create_deck(deck_number):
card_values = []
for i in range(1, deck_number + 1):
card_values.append(i)
return card_values

# Shuffle function
def shuffle(deck):

# Split deck and initialize list
half_1 = deck[0: int(len(deck)/2)]
half_2 = deck[int(len(deck)/2): len(deck)]
shuffled_deck = []

# Main shuffle loop
for i in range(len(half_1)):
shuffled_deck.append(half_1[i])
shuffled_deck.append(half_2[i])

return shuffled_deck

# Initial shuffle
next_shuffle = shuffle(create_deck(deck_size))
shuffle_count = 1

# Mainloop
while True:
if next_shuffle == create_deck(deck_size):
break
next_shuffle = shuffle(next_shuffle)
shuffle_count += 1

# Print output
print(f"For a deck of {deck_size} cards, it takes {shuffle_count} perfect shuffles to return to "
f"its original permutation.")
print("=" * 40)
``````

=====================================

OUTPUT

For a deck of 2 cards, it takes 1 perfect shuffles to return to its original permutation.

For a deck of 4 cards, it takes 2 perfect shuffles to return to its original permutation.

For a deck of 6 cards, it takes 4 perfect shuffles to return to its original permutation.

For a deck of 8 cards, it takes 3 perfect shuffles to return to its original permutation.

For a deck of 10 cards, it takes 6 perfect shuffles to return to its original permutation.

For a deck of 12 cards, it takes 10 perfect shuffles to return to its original permutation.

12. matthew said

@Sam – to format code, put ‘[code lang=”python”]’ on a line at the start of the block of code, and ‘[/code]’ on a line at the end.

13. matthew said

Just to be clear – don’t include the single quotes there, just the square brackets and the stuff inside:

```[code lang="python"]
fib = lambda n: 1 if n <= 1 else fib(n-1)+fib(n-2)
[/code]
```
14. mclrhn said

Further;If the aim of shuffling is to make the card order unpredictable or at least as unpredictable as possible ;
how many “faro-shuffles” of a 52-card stack is ideal ?….sorry about such a late comment , it was stimulated by the current array shuffling problem even though it has no relation to it !
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}