Riffle Shuffle

A Shuffle, also called a Faro Shuffle, in which a deck of cards is divided into twoHalves which are then alternatively interleaved from the left and right hands (an ``in-shuffle'') or fromthe right and left hands (an ``out-shuffle''). Using an ``in-shuffle,'' a deck originally arranged as 1 2 3 4 5 6 7 8would 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 areused 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 areperfectly interlaced). Ramnath and Scully (1996) give an algorithm for the shortest sequence of in- and out-shuffles to movea 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.

• Miller's Algorithm
• Miller's Primality Test
• Miller's Solid
• Milliard
• Millin Series
• Million
• Mills' Constant
• Milne's Method
• Milnor's Conjecture
• Milnor's Theorem
• Minimal Cover
• Minimal Discriminant
• Minimal Matrix
• Minimal Residue
• Minimal Set
• Minimal Surface
• Minimax Approximation
• Minimax Polynomial
• Minimax Theorem
• Minimum
• Minkowski-Bouligand Dimension
• Minkowski Convex Body Theorem
• Minkowski Geometry
• Minkowski-Hlawka Theorem
• Minkowski Integral Inequality