## Riffle Shuffle

A Shuffle, also called a Faro Shuffle, in which a deck of 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 moves to the position originally occupied by the th card (mod ). Therefore, in-shuffling cards times (where is Prime) results in the original card order. Similarly, out-shuffling cards times (where 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 to position . This algorithm works for any deck with an Even number of cards and is .

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 to Position 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.