主题
Search

洗牌


洗牌,也称为法罗洗牌,是一种洗牌方式,其中一副 2n 张牌的牌堆被分成两个一半。牌堆的上半部分放在左手中,然后牌从左手和右手(内洗)或从右手和左手(外洗)交替地交错。使用内洗,最初排列为 1 2 3 4 5 6 7 8 的牌堆将变为 5 1 6 2 7 3 8 4。使用外洗,牌堆顺序将变为 1 5 2 6 3 7 4 8。洗牌用于纸牌魔术(Marlo 1958ab, Adler 1973),也用于并行处理理论(Stone 1971, Chen et al. 1981)。

洗牌操作在 Wolfram 语言中实现为

  Riffle @@ Partition[Range[n], n/2, n/2, 1, {}]

一般来说,牌 k 移动到最初由第 2k 张牌占据的位置,模 2n+/-1。对于内洗,第一张牌编号为 1,乘法运算以 2n+1 为模进行。对于外洗,第一张牌编号为 0,乘法运算以 2n-1 为模进行。请注意(在外洗情况下),这会将第一张牌和最后一张牌映射为 0,但这很有意义,因为它们都是不动点。

因此,当 n+1 为素数时,内洗偶数 n 张牌 n 次会使牌恢复到原始顺序。类似地,当 n-1 为素数时,外洗偶数 n 张牌 n-2 次会使牌恢复到原始顺序 (Diaconis et al. 1983, Conway and Guy 1996)。一副普通的 52 张牌的牌堆在 52 次内洗后会恢复到原始顺序,但仅在八次外洗后就会恢复!

Aldous (1983) 表明,3/2log_2n (纠正了一个错字) 次洗牌足以使大型 n-张牌的牌堆随机化,对于一副 52 张的牌堆,需要八到九次洗牌。当与 Aldous 和 Diaconis (1986) 的结果结合时,该分析表明,需要七次洗牌才能接近随机 (Aldous and Diaconis 1986, Bayer and Diaconis 1992)。这介于洗牌次数太少和洗牌次数过多导致效果降低之间。

Morris (1994) 讨论了完美洗牌的各个方面(其中牌堆被精确地切成两半,并且牌被完美地交错)。Ramnath 和 Scully (1996) 给出了将牌从任意位置 i 移动到位置 j 的最短的内洗和外洗序列的算法。此算法适用于任何牌数为偶数的牌堆,并且复杂度为 O(log_2n)


另请参阅

纸牌, 洗牌

使用 Wolfram|Alpha 探索

WolframAlpha

更多尝试

参考文献

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.

在 Wolfram|Alpha 上被引用

洗牌

请引用为

韦斯坦因,埃里克·W. "洗牌。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/RiffleShuffle.html

学科分类