TOPICS
Search

Riffle Shuffle


A riffle shuffle, also called the Faro shuffle, is a shuffle in which a deck of 2n 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 k moves to the position originally occupied by the 2kth card modulo 2n+/-1. For an in-shuffle, the first card is numbered 1 and the multiplication is done modulo 2n+1. For an out-shuffle, the first card is numbered 0 and the multiplication is done modulo 2n-1. 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 n cards n times when n+1 is prime results in the original card order. Similarly, out-shuffling an even number n cards n-2 times when n-1 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 3/2log_2n (correcting a typo) shuffles are sufficient to randomize a large n-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 i to position j. This algorithm works for any deck with an even number of cards and is O(log_2n).


See also

Cards, Shuffle

Explore with Wolfram|Alpha

References

Adler, I. "Make Up Your Own Card Tricks." J. Recr. Math. 6, 87-91, 1973.Aldous, D. Random Walks on Finite Groups and Rapidly Mixing Markov Chains. Berlin: Springer-Verlag, pp. 243-297, 1983.Aldous, D. and Diaconis, P. "Shuffling Cards and Stopping Times." Amer. Math. Monthly 93, 333-348, 1986.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 323-325, 1987.Bayer, D. and Diaconis, P. "Trailing the Dovetail Shuffle to Its Lair." Ann. Appl. Probability 2, 294-313, 1992.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.Golomb, S. W. "Permutations by Cutting and Shuffling." SIAM Rev. 3, 293-297, 1961.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. The 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. "Practitioner's Commentary: Card Shuffling." UMAP J. 15, 333-338, 1994.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.Sloane, N. J. A. Sequences A059953 and A059954 in "The On-Line Encyclopedia of Integer Sequences."Stone, H. S. "Parallel Processing with the Perfect Shuffle." IEEE Trans. Comput. 2, 153-161, 1971.

Referenced on Wolfram|Alpha

Riffle Shuffle

Cite this as:

Weisstein, Eric W. "Riffle Shuffle." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RiffleShuffle.html

Subject classifications