費雪－耶茨洗牌演算法：隨機分組背後最公平的排列法則

如果你想用電腦把一份名單隨機分成幾個小組，不管是課堂上的學生、培訓工作坊的學員，或是線上會議的參與者，背後幾乎一定會用到費雪－耶茨洗牌演算法（Fisher-Yates Shuffle）。它是一個歷史悠久、證明嚴謹的隨機排列方法，能保證每一種可能的排列結果出現的機率完全相同。這篇文章會從實際問題出發，一步步拆解它的原理、步驟、公平性，以及它如何在我們的隨機分組工具中發揮作用。

為什麼你需要一個真正公平的洗牌演算法？

許多教師和培訓師都有過這樣的經驗：手動分組時，即使自認為隨機，也難免受到潛意識影響，總是某些人常被分到同一組，或者前排的同學總是被先點到。這種偏差長期下來會影響學員的體驗與公平感。要真正打破所有既定的順序，只能依靠具有數學保證的隨機排列方法。

費雪－耶茨洗牌演算法就是為了解決這個問題而生。它將一份名單視為一副撲克牌，通過有限步驟將順序完全打亂，讓每個最終排列的產生機率完全相等。因為這種絕對的公平性，它被廣泛應用在電腦科學、統計學、遊戲開發以及我們日常使用的隨機工具中。當你在 隨機分組產生器 中點擊「生成分組」時，系統就是利用這個演算法來確保每一組的組成是真正隨機且不受人為干擾的。

什麼是費雪－耶茨洗牌演算法？

費雪－耶茨洗牌演算法最早由統計學家羅納德·費雪（Ronald Fisher）和弗蘭克·耶茨（Frank Yates）在 1938 年提出。起初它是一種用於隨機排列數據的物理操作流程，後來被電腦科學家改寫成效率更高的程式碼版本，也就是今天我們所熟悉的「現代費雪－耶茨洗牌」。

這個演算法的核心概念非常直觀：從最後一個位置開始，隨機抽取一個範圍內的項目與該位置交換，然後往前一個位置重複同樣的動作，直到所有位置都處理完畢。這就像你手裡有一疊牌，每次都從剩下的牌中隨機抽一張放進新的牌堆，只是現代方法直接在原陣列上完成交換，節省記憶體。

直觀理解：從最後一項開始往前的隨機交換

為了真正理解這個演算法，我們可以脫離程式碼，用一個簡單的例子來想像。假設有五位學生：A、B、C、D、E，我們要將他們的順序打亂。

• 第一步，我們看第五個位置（最後一個位置）。從第 1 到第 5 個位置中隨機選一個，假設選到第 2 個位置（B），就把 B 和 E 交換。現在順序變成 A、E、C、D、B。
• 第二步，看第四個位置。從第 1 到第 4 個位置中隨機選一個，假設選到第 3 個位置（C），就把 C 和 D 交換。順序變成 A、E、D、C、B。
• 第三步，看第三個位置。從第 1 到第 3 個位置中隨機選一個，假設選到第 1 個位置（A），就把 A 和 D 交換。順序變成 D、E、A、C、B。
• 第四步，看第二個位置。從第 1 到第 2 個位置中隨機選一個，假設選到第 2 個位置（E），就不動（自己與自己交換）。
• 第五步只剩一個位置，直接保留。最終順序就是 D、E、A、C、B。

在這個過程中，每一個位置都與一個完全隨機的來源交換，並且已經交換到後面的項目不再參與後續的隨機選取。這種做法保證了每一種排列結果的機率都是 1/n!，也就是說，對五位學生來說，任何一種順序出現的機率都是完全相等的。

演算法的正式步驟與偽代碼

在許多程式語言中，現代費雪－耶茨洗牌的實作非常精簡。假設我們有一個大小為 n 的陣列，索引從 0 到 n-1：

1. 從 i = n-1 開始，向下執行到 i = 1。
2. 產生一個在 0 到 i 之間（包含 i）的隨機整數 j。
3. 交換陣列中索引 i 和索引 j 的元素。
4. 遞減 i，重複步驟 2-3。

用口語解釋就是：對於每一個位置，從該位置及其之前的範圍內隨機挑選一個元素，然後放到該位置上。因為被放到後方的元素不再移動，所以每個元素被選中的機率非常均勻。

以下是一個非常接近人類語言的偽代碼：

procedure fisher_yates_shuffle(array):
  for i from array length down to 1 do
    j ← random integer such that 0 ≤ j ≤ i
    swap array[i] with array[j]
  end for
end procedure

請注意，這裡我們假設陣列索引從 0 開始，所以當長度為 n 時，最後一個索引是 n-1。實際編寫程式時會像這樣：

for i = n-1 down to 1:
    j = random(0, i)
    swap(arr[i], arr[j])

這種寫法不僅程式碼簡短，而且時間複雜度為 O(n)，非常有效率。

為什麼它保證公平？透過機率論證

你可能會懷疑，這種交換方式真的能給出均等的排列機率嗎？答案是肯定的。我們可以這樣理解：第一個被放到最後位置的元素是從 n 個元素中均勻隨機選出的，所以每個元素有 1/n 的機率被放在最後。接下來，倒數第二個位置是從剩下的 n-1 個元素中均勻隨機選出的，因此給定之前發生的結果，每個剩餘元素被放在該位置的機率是 1/(n-1)。依此類推，最後一個位置只剩下一個元素，機率為 1。

將所有步驟的條件機率相乘，得到任何一種特定排列的機率都是 (1/n) × (1/(n-1)) × ... × 1 = 1/n!。這就是排列總數 n! 的倒數，因此每一種順序都有完全相同的可能。

另一個常見的誤解是以為「隨機抽取並放到新陣列」的方法也能達到公平，但若實作不當（例如每次都從全部範圍隨機挑選且不刪除已選元素），就可能導致重複或偏差。現代費雪－耶茨直接在原陣列上進行，步驟明確定義了機率空間，所以能保證公平，這也是許多系統庫（如 Python 的 random.shuffle()）直接採用這個演算法的原因。

與其他隨機化方法的比較

除了費雪－耶茨，還有一些常見的隨機化方式，但它們往往隱含著不完美的公平性：

• 排序法（給每個元素一個隨機鍵值再排序）：雖然通常能產生均勻結果，但依賴排序演算法的穩定性與隨機鍵值的品質；在某些邊界情況下（如鍵值重複）可能略有不均，且時間複雜度為 O(n log n)，比 O(n) 的費雪－耶茨慢。
• 簡單隨機交換（重複多次隨機交換兩個位置）：如果沒有精確控制交換次數和選擇範圍，很難保證所有排列的機率相等，且存在週期性與不均勻的風險。
• 水塘抽樣（Reservoir Sampling）：主要用於從未知大小的資料流中選取固定數量的樣本，與排列是不同目的，不適合直接做為洗牌工具。

對於分組工具來說，我們需要的是快速且嚴謹公平的排列，費雪－耶茨無疑是最佳選擇。它也簡短到幾乎不可能出錯，因此被視為教科書等級的演算法。

在隨機分組產生器中的實際應用

在我們的 隨機分組產生器 中，每次你貼上一份名單並點擊產生分組，後端會依序進行以下過程：

1. 將名單中的所有人員轉換成一個有序清單。
2. 使用費雪－耶茨洗牌演算法徹底打亂這個清單。
3. 將打亂後的人員依次分配到你所設定的組數中（例如每組 4 人則每 4 人一組）。

因為洗牌的公平性，你可以完全信任分組結果，不用擔心某些組合出現頻率過高，也不必擔心順序偏誤。同樣地，我們的 隨機配對產生器 和 隨機學生點名器 也是基於相同的公平洗牌核心，確保每一次的產出都經得起數學檢驗。

實作時需要注意的細節

雖然費雪－耶茨洗牌在概念上非常簡單，但程式實作時仍有幾個常見的陷阱值得留意：

• 隨機數產生器的品質：如果隨機數產生器有偏差或可預測性，洗牌結果也會有偏差。現代程式語言大多提供密碼學安全的隨機數函式庫，在需要高度隨機性時可以採用。
• 索引範圍的正確性：隨機數 j 一定要從 0 到 i 之間（包含 i），也就是 [0, i]。若範圍誤設為 [0, i-1]，將導致最後一個元素永遠不會被選中，破壞公平性。
• 不使用不當的隨機排序法：許多新手會使用 array.sort(() => Math.random() - 0.5)，這種方式不僅效能較差，而且在某些排序引擎下可能產生不均勻的分佈，不應使用。

只要留意這些細節，費雪－耶茨就是一個能夠完美勝任隨機排列任務的可靠演算法。

常見問題

費雪－耶茨洗牌可以處理非常大量的名單嗎？

可以，因為它的時間複雜度是 O(n)，而且直接在原陣列上進行，空間複雜度是 O(1)。所以即使是數萬人的名單，也能在瞬間完成洗牌。當然，最終的效能還取決於隨機數產生器的速度，但對日常分組規模完全不是問題。

這個演算法和洗撲克牌的方式一樣嗎？

非常類似。原始版本模擬了人手工洗牌的過程——隨機抽出一張牌放到新的牌堆。而現代版本則是在同一疊牌上進行交換，效率更高。兩者在機率上都是均勻公平的。

如果我只是要隨機選幾個人出來，還需要用費雪－耶茨嗎？

如果你只需要選出少數幾個人（例如點一位學生），可以只進行部分洗牌：執行費雪－耶茨的前 k 步，就等於從 n 個元素中隨機抽出 k 個且不重複。我們的 隨機學生點名器 就是這樣運作的。

為什麼不用簡單的「隨機挑一個數字」來排列就好了？

如果直接對每個位置隨機指定一個號碼再排序，除了較慢之外，還需要處理號碼重複與排序穩定性的問題。費雪－耶茨直接在步驟中定義機率空間，更簡單且保證正確。

這個演算法的名稱是固定的嗎？

在英文中被稱為 Fisher–Yates shuffle 或 Knuth shuffle，因為唐納德·克努斯（Donald Knuth）在他的《計算機程式設計藝術》中推廣了現代版本。中文裡通常直接稱費雪－耶茨洗牌或克努斯洗牌。

結語：讓公平的隨機性成為你的日常工作夥伴

了解費雪－耶茨洗牌演算法之後，你會發現真正的公平隨機並非靠運氣，而是靠嚴謹的數學設計。無論你是教師、培訓師還是活動策劃者，下次當你需要公正地將人員分配成小組或挑選學生時，可以放心地依靠經過驗證的演算法，而不是人手抽籤或依靠直覺。

我們的平台已經將這個演算法內建在所有工具中，你只需要專注在活動的內容與互動上。現在就前往 隨機分組產生器，貼上你的名單，體驗真正公平、快速、零偏差的分組過程吧。