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).
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 .
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. Monthly93, 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. Probability2, 294-313, 1992.Chen, P. Y.; Lawrie,
D. H.; Yew, P.-C.; and Padua, D. A. "Interconnection Networks Using
Shuffles." Computer33, 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 to Position 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.