洗牌

洗牌，也稱為法羅洗牌，是一種洗牌方式，其中一副 張牌的牌堆被分成兩個一半。牌堆的上半部分放在左手中，然後牌從左手和右手（內洗）或從右手和左手（外洗）交替地交錯。使用內洗，最初排列為 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, {}]

一般來說，牌 移動到最初由第 張牌佔據的位置，模 。對於內洗，第一張牌編號為 1，乘法運算以 為模進行。對於外洗，第一張牌編號為 0，乘法運算以 為模進行。請注意（在外洗情況下），這會將第一張牌和最後一張牌對映為 0，但這很有意義，因為它們都是不動點。

因此，當 為素數時，內洗偶數 張牌 次會使牌恢復到原始順序。類似地，當 為素數時，外洗偶數 張牌 次會使牌恢復到原始順序 (Diaconis et al. 1983, Conway and Guy 1996)。一副普通的 52 張牌的牌堆在 52 次內洗後會恢復到原始順序，但僅在八次外洗後就會恢復！

Aldous (1983) 表明， (糾正了一個錯字) 次洗牌足以使大型 -張牌的牌堆隨機化，對於一副 52 張牌的牌堆，需要八到九次洗牌。當與 Aldous 和 Diaconis (1986) 的結果結合時，該分析表明，需要七次洗牌才能接近隨機 (Aldous and Diaconis 1986, Bayer and Diaconis 1992)。這介於洗牌次數太少和洗牌次數過多導致效果降低之間。

Morris (1994) 討論了完美洗牌的各個方面（其中牌堆被精確地切成兩半，並且牌被完美地交錯）。Ramnath 和 Scully (1996) 給出了將牌從任意位置 移動到位置 的最短的內洗和外洗序列的演算法。此演算法適用於任何牌數為偶數的牌堆，並且複雜度為 。