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
    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:

    (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

    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         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}:*[]}
    :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
    :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}:*[]}
    :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
    :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 !

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: