I can never shuffle cards properly. They seem to go every which way when I try, and a perfect random shuffle seems nigh-impossible to achieve, even though the experts claim it takes a mere 7 moves. (The mathematical argument is surprisingly quite technical.) Luckily, we shall concern ourselves with a much simpler problem today: How many perfect out-shuffles does it take to restore a deck back to its original order? We’ll throw in a couple of variants of the problem for fun, but rest assured that we’ll let computers do the work. And, of course, we’ll use Cryptol to help us along the way.
What is a riffle shuffle?
According to wikipedia, a riffle (or dovetail) shuffle goes like this:
… half of the deck is held in each hand with the thumbs inward, then cards are released by the thumbs so that they fall to the table interleaved. Many also lift the cards up after a riffle, forming what is called a bridge which puts the cards back into place…
Well, I read that a couple times, and watched a couple of videos on the internet showing how to do it, but no luck so far. Luckily, this sort of shuffling is quite easy to express programmatically, and Cryptol has the right abstractions to code this in a couple of lines.
Bisecting the deck
The first step in the shuffle is bisecting the deck into two equal halves:
bisect : {a b} (fin a) => [2*a]b -> ([a]b, [a]b);bisect xs = (take (w, xs), drop (w, xs))where w = width xs / 2;
We simply compute the mid-point, and divide the given sequence xs into two, by take‘ing and drop‘ping the correct amounts from the input sequence. In fact, the type of bisect is more interesting than its definition: It succinctly captures the following four facts:
- The input has to be of even length (2*a),
- The input has to be finite (fin a),
- The output has two components, each of which has precisely a elements, that is, half the input,
- The actual contents of the sequence can be of any type (b), i.e., the function bisect is shape-polymorphic in the contents.
The ability to express precise size/shape-polymorphic properties using types is one of the strengths of Cryptol.
Out-shuffle vs in-shuffle
Once the deck is split into two, we proceed by picking the cards alternatingly from each half. We have two choices: We can either start with the first half, or the second. If you start with the first half, that’s called an out-shuffle. If you start with the second half, then it’s an in-shuffle. These two functions are actually quite easy to code in Cryptol:
outShuffle : {a b} (fin a) => [2*a]b -> [2*a]b;outShuffle xs = join [| [x y] || x <- fh || y <- sh |]where (fh, sh) = bisect xs;inShuffle : {a b} (fin a) => [2*a]b -> [2*a]b;inShuffle xs = join [| [y x] || x <- fh || y <- sh |]where (fh, sh) = bisect xs;
The definitions are almost identical, except for the order in which we put the cards from the halves (fh and sh) together. In the outShuffle, the first card in each pair comes from the first-half. In the inShuffle, it comes from the second half. Easier done than said! Let’s make sure they behave as we expect:
Cryptol> bisect [1..8]([1 2 3 4], [5 6 7 8])Cryptol> outShuffle [1..8][1 5 2 6 3 7 4 8]Cryptol> inShuffle [1..8][5 1 6 2 7 3 8 4]
Good! It’s interesting to see what happens when we apply bisect to an odd-length sequence:
Crytpol> bisect [1..9]In a top-level expression: with inferred type:{a} ([a][4],[a][4])encountered the following unresolved constraints:fin a2*a == 9
Cryptol is basically telling us that there is no a such that 2*a is 9, resulting in a type-error. Note that this is a static-check before you run your program! In other words, if your program type-checks, then you can rest assured that whenever you call bisect, it is guaranteed to get an even-length sequence as its argument. Strong static typing and size-polymorphism of Cryptol really pays off in this case!
Sequences of shuffles
Before proceeding to the properties of shuffles, we need one last notion: The application of a shuffle repeatedly to a given input, yielding an infinite sequence of transformations:
iterate : {a} (a -> a, a) -> [inf]a;iterate (f, x) = [x] # iterate (f, f x);outShuffles, inShuffles :{a b} (fin a) => [2*a]b -> [inf][2*a]b;outShuffles xs = iterate(outShuffle, xs);inShuffles xs = iterate(inShuffle, xs);
The high-order function iterate gives us the infinite sequence of results of applying a function to a value over and over. We simply use this helper to define outShuffles and inShuffles to apply the corresponding functions indefinitely to their input. Note that the resulting type shows that we get an infinite sequence as output, as indicated by the size inf.
Properties of shuffles
It turns out that if one applies 8 out-shuffles to a deck, a remarkable thing happens: Nothing! The deck goes back to its original order! This is a bit hard to believe, and harder to realize using a real deck of cards. (A friend of mine says he saw it done at college once by hand, but I’m yet to meet anyone who can do this successfully so far!)Well, the good thing about programming is that we can manipulate the sequences at will, without fear of messing up the cards. Even better, we can assert the above claim as a theorem in Cryptol:
type Deck = [52][6];outShuffle8 : Deck -> Bit;theorem outShuffle8: {deck}.outShuffles(deck) @ 8 == deck;
We have defined a Deck to be a sequence of 52 things, each of which is 6-bits wide, which is more than enough to cover all the 52-unique elements that appear in an ordinary deck. (6-bits can encode 64 values, so we have 12 unused elements.) The theorem simply states that the 8’th element of the infinite sequence of outShuffle applied to an arbitrary deck gives us back the original deck.Let’s ask Cryptol to prove this theorem: (Cryptol’s symbolic and sbv backends can perform these proofs, so we first set our mode accordingly below.)
Cryptol> :set sbvCryptol> :prove outShuffle8Q.E.D.
Voila! The proof completes instantaneously, with almost no time elapsed. (This might be surprising at first, since the input space to the theorem has 52*6 = 312 bits, which is quite large. However, we note that the theorem is actually fairly easy to prove since all shuffling does is a mere re-ordering of things with no specific computation; which is easy to manipulate symbolically for Cryptol’s proof engine.)
Reversing the deck
Can we reverse a deck of cards using outShuffle‘s? Turns out that this cannot be done. In particular, an outShuffle never moves the first element of the deck anywhere:
outShuffleFirstCard : Deck -> Bit;theorem outShuffleFirstCard: {deck}.outShuffle deck @ 0 == deck @ 0;
We have:
Cryptol> :prove outShuffleFirstCardQ.E.D.
Since the first card remains stationary, there is no way to reverse a deck of cards by just using outShuffles.How about with inShuffle? Turns out the magic number is 26 for reversing a deck of cards in this particular case:
inShuffle26Rev : Deck -> Bit;theorem inShuffle26Rev : {deck}.inShuffles(deck) @ 26 == reverse deck;
Again, the proof is immediate:
Cryptol> :prove inShuffle26RevQ.E.D.
If 26 in-shuffle’s reverse the deck, then 52 of them will restore it back. Here’s the corresponding theorem:
inShuffle52 : Deck -> Bit;theorem inShuffle52: {deck}.inShuffles(deck) @ 52 == deck;
Again, the proof is immediate.
The Mongean Shuffle
There is one more variation on the shuffle that we w
ill consider. The mongean shuffle picks the even and odd numbered elements, reverses the odds and adds the evens at the back. For instance, given the sequence: 0 1 2 3 4 5 6 7 8 9, we first construct two sub-sequences: The even index elements: 0 2 4 6 8, and the odd ones 1 3 5 7 9. We then reverse the latter to get 9 7 5 3 1, and append the former, obtaining: 9 7 5 3 1 0 2 4 6 8. Luckily, the Cryptol definition is much easier to read:
monge xs = reverse odds # evenswhere { w = width xs;evens = xs @@ [0 2 .. (w-1)];odds = xs @@ [1 3 .. (w-1)]};monges xs = iterate(monge, xs);
With a monge shuffle, it takes 12 rounds to restore a deck:
monge12 : Deck -> Bit;theorem monge12: {deck}. monges(deck) @ 12 == deck;
We will leave it to the reader to construct the argument that no sequence of monge shuffles would reverse a deck. (In particular, one can prove that the 18th element from top will never move in a deck of 52. Proving this theorem in Cryptol is again quite trivial.)
A note on theorems
The attentive reader might worry that our Deck type does not quite correspond to a deck-of-cards. This is indeed the case. There are two discrepancies. First, as we mentioned before, our decks can represent 64 elements, while a deck of cards has only 52 distinct cards. On the plus side, this just makes our theorems “stronger,” since we allow for more cards then possible. More importantly, the properties are intended for decks that have no-repeating cards in them. (That is, every card occurs precisely once.) But our theorems apply to arbitrary deck‘s, even those that have repeating elements in them. Again, this just makes our theorems stronger, as the unique-sequence cases directly follow from them. We can rest assured that our proofs are conclusive, even though our model of playing-cards is not perfect.
Download
Free evaluation licenses of Cryptol are available at www.cryptol.net. The Cryptol source code for shuffling cards is also available as well.
3 7 0 2 5 1 6 4