Riffle Shuffle

A Shuffle, also called a Faro Shuffle, in which a deck of $2n$ cards is divided into two Halves which 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).

In general, card $k$ moves to the position originally occupied by the $2k$th card (mod $2n+1$). Therefore, in-shuffling $2n$ cards $2n$ times (where $2n+1$ is Prime) results in the original card order. Similarly, out-shuffling $2n$ cards $2n-2$ times (where $2n-1$ is Prime) results in the original order (Diaconis et al. 1983, Conway and Guy 1996). Amazingly, this means that an ordinary deck of 52 cards is returned to its original order after 8 out-shuffles.

Morris (1994) further 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 $i$ to position $j$. This algorithm works for any deck with an Even number of cards and is ${\mathcal O}(\log n)$.

See also Cards, Shuffle

References

Adler, I. ``Make Up Your Own Card Tricks.'' J. Recr. Math. 6, 87-91, 1973.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 323-325, 1987.

Chen, P. Y.; Lawrie, D. H.; Yew, P.-C.; and Padua, D. A. ``Interconnection Networks Using Shuffles.'' Computer 33, 55-64, Dec. 1981.

Conway, J. H. and Guy, R. K. ``Fractions Cycle into Decimals.'' In The Book of Numbers. New York: Springer-Verlag, pp. 163-165, 1996.

Diaconis, P.; Graham, R. L.; and Kantor, W. M. ``The Mathematics of Perfect Shuffles.'' Adv. Appl. Math. 4, 175-196, 1983.

Gardner, M. Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. Washington, DC: Math. Assoc. Amer., 1989.

Herstein, I. N. and Kaplansky, I. Matters Mathematical. New York: Harper & Row, 1974.

Mann, B. ``How Many Times Should You Shuffle a Deck of Cards.'' UMAP J. 15, 303-332, 1994.

Marlo, E. Faro Notes. Chicago, IL: Ireland Magic Co., 1958a.

Marlo, E. Faro Shuffle. Chicago, IL: Ireland Magic Co., 1958b.

Medvedoff, S. and Morrison, K. ``Groups of Perfect Shuffles.'' Math. Mag. 60, 3-14, 1987.

Morris, S. B. and Hartwig, R. E. ``The Generalized Faro Shuffle.'' Discrete Math. 15, 333-346, 1976.

Peterson, I. Islands of Truth: A Mathematical Mystery Cruise. New York: W. H. Freeman, pp. 240-244, 1990.

Ramnath, S. and Scully, D. ``Moving Card $i$ to Position $j$ with Perfect Shuffles.'' Math. Mag. 69, 361-365, 1996.

Stone, H. S. ``Parallel Processing with the Perfect Shuffle.'' IEEE Trans. Comput. 2, 153-161, 1971.