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).
The riffle operation is implemented in Mathematica as Riffle@@Partition[Range[n], n/2,
n/2, 1,   ].
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. 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  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.
|
Contact the MathWorld Team
