Consider a deck of $2 n$ cards. There exists a bijection from the set of cards to the finite set $\{1, 2, \dots, 2 n\}$, which allows us to represent the deck using a ($2 n$)-tuple, as follows

$(1, 2, \dots, n, n+1, n+2, \dots, 2 n)$

where the first element represents the card at the top of the deck, and the ($2 n$)-th element represents the card at the bottom of the deck. A perfect shuffle consists of cutting the deck exactly in half and then interlacing / interleaving the two halves perfectly. The in shuffle moves the original top card to the second position. The out shuffle leaves the original top card on top [1]. After a perfect in shuffle the deck will be

$(n+1, 1, n+2, 2, \dots, 2 n, n)$,

whereas after a perfect out shuffle the deck will be

$(1, n+1, 2, n+2, \dots, n, 2 n)$.

Is it possible to restore the deck to its original order after a certain number of perfect shuffles? Amazingly (or perhaps not), it is indeed possible!

__________

Example 1

Suppose we are given a deck of $8$ cards (i.e., $n = 4$). A perfect out shuffle of this deck is depicted below

[ source ]

Using pencil and paper, it is easy to see that after three perfect out shuffles the deck will be restored to its original order. Here is a Haskell script:

```-- create Card data type
data Card = Ace | Two | Three | Four |
Five | Six | Seven | Eight
deriving (Show, Eq)

-- create type synonym
type Deck = [Card]

-- interlace two decks of the same size
interlace :: Deck -> Deck -> Deck
interlace [] [] = []
interlace (c1:d1) (c2:d2) = [c1,c2] ++ interlace d1 d2

-- perfect out shuffle
outShuffle :: Deck -> Deck
outShuffle deck = interlace deck1 deck2
where deck1 = fst (splitAt 4 deck)
deck2 = snd (splitAt 4 deck)

-- perfect in shuffle
inShuffle :: Deck -> Deck
inShuffle deck = interlace deck2 deck1
where deck1 = fst (splitAt 4 deck)
deck2 = snd (splitAt 4 deck)```

where I used function splitAt to cut the deck into two halves of equal size. Since I am not acquainted with any function that performs interleaving, I did create my own function. We load this script into GHCi. Here is a brief GHCi session:

```*Main> -- create deck
*Main> let deck = [Ace,Two,Three,Four,Five,Six,Seven,Eight]
*Main> -- perform 3 out shuffles
*Main> take 4 (iterate outShuffle deck)
[[Ace,Two,Three,Four,Five,Six,Seven,Eight],
[Ace,Five,Two,Six,Three,Seven,Four,Eight],
[Ace,Three,Five,Seven,Two,Four,Six,Eight],
[Ace,Two,Three,Four,Five,Six,Seven,Eight]]
*Main>```

Indeed, after three perfect out shuffles, we do obtain a deck in the original order! One is tempted to wonder what the order of the deck will be after three perfect in shuffles. Let us see:

```*Main> -- create deck
*Main> let deck = [Ace,Two,Three,Four,Five,Six,Seven,Eight]
*Main> -- perform 3 in shuffles
*Main> take 4 (iterate inShuffle deck)
[[Ace,Two,Three,Four,Five,Six,Seven,Eight],
[Five,Ace,Six,Two,Seven,Three,Eight,Four],
[Seven,Five,Three,Ace,Eight,Six,Four,Two],
[Eight,Seven,Six,Five,Four,Three,Two,Ace]]```

After three perfect in shuffles we do not obtain the original deck. Instead, we obtain a reversal of the original deck.

__________

Example 2

Let us now work with the standard deck of $52$ cards. People say that eight consecutive perfect out shuffles will restore the deck to its original order. Let us check whether this is true or not.

Here is a new Haskell script:

```-- create Value data type
data Value = Ace | Two | Three | Four | Five | Six | Seven | Eight |
Nine | Ten | Jack | Queen | King deriving (Show, Eq)

-- create Suit data type
data Suit  = Club | Diamond | Heart | Spade deriving (Show, Eq)

-- create type synonyms
type Card = (Value,Suit)
type Deck = [Card]

-- create list of card values
values :: [Value]
values = [Ace,Two,Three,Four,Five,Six,Seven,
Eight,Nine,Ten,Jack,Queen,King]

-- create list of card suits
suits :: [Suit]

-- create deck
deck :: Deck
deck = [(v,s) | v <- values, s <- suits]

-- interlace two decks of the same size
interlace :: Deck -> Deck -> Deck
interlace [] [] = []
interlace (c1:d1) (c2:d2) = [c1,c2] ++ interlace d1 d2

-- perfect out shuffle
outShuffle :: Deck -> Deck
outShuffle deck = interlace deck1 deck2
where n = div (length deck) 2
deck1 = fst (splitAt n deck)
deck2 = snd (splitAt n deck)

-- perfect in shuffle
inShuffle :: Deck -> Deck
inShuffle deck = interlace deck2 deck1
where n = div (length deck) 2
deck1 = fst (splitAt n deck)
deck2 = snd (splitAt n deck)```

We load this script into GHCi. Here is a GHCi session:

```*Main> -- print deck
*Main> deck
*Main> -- perform 8 out shuffles
*Main> let deck8 = (iterate outShuffle deck) !! 8
*Main> -- is the new deck the same as the original one?
*Main> deck8 == deck
True```

Indeed, it is true! Eight perfect out shuffles suffice!

__________

References

[1] Persi Diaconis, R. L. Graham, William M. Kantor, The Mathematics of Perfect Shuffles, Advances in Applied Mathematics, Volume 4, Issue 2, June 1983.

### 6 Responses to “Perfect shuffles in Haskell”

1. Carsten Says:

well either I don’t understand the problem correctly or it’s indeed trivial (that you can perfect-shuffle back to the starting-deck): it’s just a bijection on a finite set – so it’s a group-element in a finite group and has of course finite-order.

• I. J. Kennedy Says:

Well of course some number of perfect shuffles will eventually restore the original order. The surprise is that number is merely 8, for a standard deck.

2. Gabriel Verret Says:

I have to agree that the fact that a finite number suffices is somewhat trivial. It arguably doesn’t even require knowledge of group theory, just the definition of a permutation and that fact that permutations are invertible.

Proof:
Suppose X is a finite set and f is a permutation on X.
Since X is finite, there exist positive integers such that f^{n+m}=f^n.
Since f is a permutation, it is invertible and we get that f^m is the identity.

(Of course, all groups are permutation group and one could argue this proof is really group theory in disguise but my point is that someone could easily understand it without knowing anything but basic naive set theory.)

What IS mildly surprising is how few perfect shuffles are really needed. For example, the proof above only gives an upper bound of |X|! for m.

I haven’t read Diaconis et al.’s book but I doubt it is just about the fact that a certain finite number of perfect shuffles will recover the original deck order.

• Rod Carvalho Says:

Respectfully, my good sir, I really do not care if it is trivial or non-trivial. This is not a Group Theory post; this was supposed to be a programming post. I am not interested in proofs (Diaconis et al. did that already), but rather in actual implementation and experimentation.

3. Jeff Says:

Can every permutation of the deck be reached via perfect shuffles and what is the distance to the farthest order via perfect shuffles?