Riffle Shuffle

A riffle shuffle, also called the Faro shuffle, is a shuffle in which a deck of cards is divided into two halves. The top half of the deck is placed in the left hand, and cards are then alternatively interleaved from the left and right hands (an in-shuffle) or from the right and left hands (an out-shuffle). Using an in-shuffle, a deck originally arranged as 1 2 3 4 5 6 7 8 would become 5 1 6 2 7 3 8 4. Using an out-shuffle, the deck order would become 1 5 2 6 3 7 4 8. Riffle shuffles are used in card tricks (Marlo 1958ab, Adler 1973), and also in the theory of parallel processing (Stone 1971, Chen et al. 1981).

The riffle operation is implemented in the Wolfram Language as:

  Riffle @@ Partition[Range[n], n/2, n/2, 1, {}]

In general, card moves to the position originally occupied by the th card modulo . For an in-shuffle, the first card is numbered 1 and the multiplication is done modulo . For an out-shuffle, the first card is numbered 0 and the multiplication is done modulo . Note that (in the out-shuffle case) this maps the first and last card to 0, but this makes sense, because they are both fixed points.

Therefore, in-shuffling an even number cards times when is prime results in the original card order. Similarly, out-shuffling an even number cards times when is prime results in the original order (Diaconis et al. 1983, Conway and Guy 1996). An ordinary deck of 52 cards is returned to its original order after 52 in-shuffles, but after only eight out-shuffles!

Aldous (1983) showed that (correcting a typo) shuffles are sufficient to randomize a large -card deck, yielding eight to nine shuffles for a deck of 52 cards. When combined with results of Aldous and Diaconis (1986), this analysis suggests that seven riffle shuffles are needed to get close to random (Aldous and Diaconis 1986, Bayer and Diaconis 1992). This is intermediate between too few shuffles and the decreasing effectiveness of too many shuffles.

Morris (1994) discusses aspects of the perfect riffle shuffle (in which the deck is cut exactly in half and cards are perfectly interlaced). Ramnath and Scully (1996) give an algorithm for the shortest sequence of in- and out-shuffles to move a card from arbitrary position to position . This algorithm works for any deck with an even number of cards and is .