Riffle shuffle

A riffle shuffle is when you shuffle a pack of playing cards such that the top half of the deck is interleaved with the bottom half. If you are able to do this perfectly, that is you can perfectly interleave the two halves of the deck of cards, then for a deck of 52 playing cards you would only need to perform 8 perfect riffle shuffles to put the deck back in the same order as you had originally started with! When Laurie told me this the other day, I couldn't believe it! Eight! So I wrote a little perl script to convince myself:

#!/usr/bin/perl
$ARGV[0] || die"usage: shuffle N\n"; $N=$ARGV[0]; for ($i=0;$i<$N;$i++) {$dA[$i]=$i+1; $dO[$i]=$dA[$i];} $k=0; do {$j=0; for ($i=0;$i<$N;$i=$i+2) {$dB[$i]=$dA[$j]; $j++;} for ($i=1;$i<$N;$i=$i+2) {$dB[$i]=$dA[$j]; $j++;} @dA=@dB; $t=1; for ($i=0;$i<$N;$i++) {if ($dA[$i]!=$dO[$i]) {$t=0;}} $k++;} while ($t==0); print $k."\n";

Sorry about the lack of comments and structure (gotta love perl ;), but the code above performs perfect riffle shuffles on an array of numbers (ie. a virtual deck of cards) until it ends up with an array that is the same as the original one (ie. the order of the shuffled deck is the same as the unshuffled one). You need to specify the number of cards in your virtual deck as an argument, and will be rewarded with the number of shuffles that were required.

And sure enough, if you specify 52 cards in your deck, then an answer of 8 shuffles is returned. Amazing! This is the same as if your deck was only composed of 18 cards. And furthermore, if your deck consisted of 54 cards (the normal 52 playing cards plus the 2 jokers), then you need to perform 52 perfect riffle shuffles to the deck in order to get back where you started!

There's a neat explanation on MathWorld (apparently what I've simulated above is an out-shuffle). I'm convinced that a group theoretic approach will yield a formula relating the number of shuffles required to the number of cards in a deck. The obsession goes on...