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.
Programming Praxis 
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!
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,Here is a simple solution in R7RS Scheme and a few popular helpers.
It includes a formulaic method for computing the cycle-length in
addition to the explicit one.
(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:
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
def perfectShuffle(arr):
orig = np.copy(arr)
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
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
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:
As indicated on Wikipedia, this matches sequence A002326 on OEIS.
Here’s a Haskell version. Instead of shuffling an actual list I use the formulas from the “Faro shuffle” Wikipedia page.
{-# LANGUAGE LambdaCase #-} import Control.Monad (forM_) 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 6732I 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))) # TrueKlong 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}:*[]} :monad 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} :monad {.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 :okKlong 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}:*[]} :monad 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} :monad {.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 :doneSorry 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)
=====================================
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.
@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.
Just to be clear – don’t include the single quotes there, just the square brackets and the stuff inside:
Racket: https://github.com/xojoc/programming-challenges/blob/master/programming-praxis/2020_03_13.rkt
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 !