Perfect shuffles in Haskell

Consider a deck of cards. There exists a bijection from the set of cards to the finite set , which allows us to represent the deck using a ()-tuple, as follows

where the first element represents the card at the top of the deck, and the ()-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

,

whereas after a perfect out shuffle the deck will be

.

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 cards (i.e., ). 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 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]
suits = [Club,Diamond,Heart,Spade]

-- 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
[(Ace,Club),(Ace,Diamond),(Ace,Heart),(Ace,Spade),
 (Two,Club),(Two,Diamond),(Two,Heart),(Two,Spade),
 (Three,Club),(Three,Diamond),(Three,Heart),(Three,Spade),
 (Four,Club),(Four,Diamond),(Four,Heart),(Four,Spade),
 (Five,Club),(Five,Diamond),(Five,Heart),(Five,Spade),
 (Six,Club),(Six,Diamond),(Six,Heart),(Six,Spade),
 (Seven,Club),(Seven,Diamond),(Seven,Heart),(Seven,Spade),
 (Eight,Club),(Eight,Diamond),(Eight,Heart),(Eight,Spade),
 (Nine,Club),(Nine,Diamond),(Nine,Heart),(Nine,Spade),
 (Ten,Club),(Ten,Diamond),(Ten,Heart),(Ten,Spade),
 (Jack,Club),(Jack,Diamond),(Jack,Heart),(Jack,Spade),
 (Queen,Club),(Queen,Diamond),(Queen,Heart),(Queen,Spade),
 (King,Club),(King,Diamond),(King,Heart),(King,Spade)]
*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.

About these ads

Tags: Card Shuffling, Card Tricks, Haskell, List Processing, Perfect Shuffle