從 Python 的 random.shuffle() 學 Fisher-Yates Shuffle / Knuth Shuffle 演算法

最近接觸了一些牌類遊戲的開發，發現如何洗牌也是 1 個學問，所以特別查了一個重要的演算法 Fisher-Yates Shuffle / Knuth Shuffle ，發現 Python 的 random.shuffle() 也使用相同的演算法實作，所以特別將 Fisher-Yates Shuffle / Knuth Shuffle 實作細節與視覺化做出來，希望可以讓不熟悉的人也能迅速上手。

本文環境 #

• Python 3

random.shuffle() 的原始碼(source code) #

Shuffle the sequence x in place.

random.shuffle() 的用途是拿來打亂 1 個 sequence (必須 mutable)的順序，例如將 [1, 2, 3] 打亂成 [3, 1, 2] ，它的特點是會直接修改原始資料，所以它不回傳任何值。

>>> from random import shuffle
>>> x = [1, 2, 3]
>>> shuffle(x)
>>> x
[2, 1, 3]

以下是 random.shuffle() 的原始碼：

def shuffle(self, x):
    """Shuffle list x in place, and return None."""

    randbelow = self._randbelow
    for i in reversed(range(1, len(x))):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = randbelow(i + 1)
        x[i], x[j] = x[j], x[i]

上述程式碼很簡短，它會從 list x 的最後 1 個元素開始往前走訪，假設此元素索引值為 i ，每次都會取 1 個小於等於 i 的隨機整數 j ( 0 <= j <= i ), 然後將元素 i 跟元素 j 進行互換，直到 i 到第 2 個元素為止。

p.s. 如果隨機整數 i == j 就代表此次迭代不交換元素，不交換也是 1 種可能性

將上述程式碼視覺化的話，如下列影片所示：

random.shuffle() 所使用的演算法就是知名的 Fisher-Yates Shuffle ，或稱 Knuth shuffle。

Fisher-Yates Shuffle 演算法 / Knuth Shuffle #

Fisher-Yates Shuffle 是由 Ronald Fisher 和 Frank Yates 共同設計的演算法。這個演算法不僅簡潔高效，其時間複雜度為 O(n), 還能夠確保每種排列組合出現的機率均等，因此，Fisher-Yates Shuffle 經常被用於牌類遊戲的洗牌。

不過 Fisher-Yates Shuffle 被廣泛認識是因為 Donald E. Knuth 在其著作《The Art of Computer Programming》中提到這個演算法。當時並沒有提到這是 Ronald Fisher 和 Frank Yates 兩人的研究成果，所以 Fisher-Yates Shuffle 也被稱為 Knuth Shuffle 。直到後來《The Art of Computer Programming》改版，才提到 Ronald Fisher 和 Frank Yates 所做的貢獻。

不用 Fisher-Yates Shuffle 會發生什麼事？ #

有人可能會想說洗牌可以每次走訪都隨機從 list 中挑 1 個元素作互換就好，例如下列程式碼：

from random import randint

def bad_shuffle(x):
    n = len(x)
    for i in range(0, n):
        j = randint(0, n - 1)
        x[i], x[j] = x[j], x[i]

但恰好就是這樣的作法造成每 1 種組合出現的機率不均等。

我們拿 ['A', 'B', 'C'] 3 個元素的 list 做實驗看看，理論上做 1,000 次 shuffle 應該要以下 6 種排列組合出現次數接近：

• ['A', 'B', 'C']
• ['A', 'C', 'B']
• ['B', 'A', 'C']
• ['B', 'C', 'A']
• ['C', 'A', 'B']
• ['C', 'B', 'A']

實驗程式碼如下：

from collections import Counter

counter = Counter()

for _ in range(0, 1000):
      x = ['A', 'B', 'C']
      bad_shuffle(x)
      counter[''.join(x)] += 1

for k, v in counter.items():
    print(f"{k}: {v/1000:.2%}")

上述程式碼執行結果如下：

ABC: 14.50%
CAB: 14.30%
BAC: 20.60%
ACB: 18.40%
BCA: 18.40%
CBA: 13.80%

可以看到 BAC 出現機率較高，甚至可以佔高達 20% 的出現機率，而 CBA 出現機率最低。

但如果改用 Fisher-Yates Shuffle 就可以感受到每種組合的出現次數比較均衡，這就是 Fisher-Yates Shuffle 所帶來的優勢，確保各種組合出現的機率較公平一致：

CBA: 16.60%
CAB: 17.00%
ABC: 16.60%
BAC: 17.10%
BCA: 16.40%
ACB: 16.30%

上述測試程式碼如下，有興趣可以參考：

from collections import Counter
import random

counter = Counter()

for _ in range(0, 1000):
      x = ['A', 'B', 'C',]
      random.shuffle(x)
      counter[''.join(x)] += 1

for k, v in counter.items():
    print(f"{k}: {v/1000:.2%}")

Fisher-Yates Shuffle 的等效作法 #

Python 所實作的 random.shuffle() 程式碼是從 list 的尾端開始走訪，但其實從頭開始走訪也沒問題，所以可以寫成：

from random import randint

def shuffle(x):
    """Shuffle list x in place, and return None."""
    n = len(x)
    for i in range(0, n - 1):
        j = randint(i, n - 1)
        x[i], x[j] = x[j], x[i]

總結 #

有些程式碼看似短短的，卻隱藏著某些大道理。

以上！

Enjoy!

References #

random — Generate pseudo-random numbers

Fisher–Yates shuffle - Wikipedia

python random shuffle knuth fisher-yates