Fisher-Yates Shuffle 演算法：公平洗牌的原理與實作

「隨機分組」聽起來簡單，但要在程式裡真正做到「完全公平」並不容易。Fisher-Yates Shuffle 演算法（又稱 Knuth Shuffle）正是資料科學中最經典的隨機排列方法，它不僅在理論上保證每種排列機會均等，實際執行效率也極高。無論是課堂小組抽籤、隨機配對還是團隊熱身遊戲，背後都常依靠這個演算法。本文將從歷史、步驟、公平性證明到實際應用，帶你徹底認識 Fisher-Yates 洗牌演算法，並了解它如何幫助你產生真正隨機的公平分組。

什麼是 Fisher-Yates 洗牌演算法？

Fisher-Yates Shuffle 最早由統計學家 Ronald Fisher 與 Frank Yates 於 1938 年在《Statistical Tables for Biological, Agricultural and Medical Research》一書中提出。最初的方法是以筆和紙運作：先隨機抽出一個數字劃掉，再從剩餘數字中隨機抽出下一個，直到所有數字都被抽出，形成一個隨機排列。這個過程雖然正確，但當列表很長時非常費時。

1964 年，電腦科學家 Richard Durstenfeld 在《Communications of the ACM》上發表了一個更適合電腦實作的改良版本。他將原本反向從未抽取元素中選取的方式，轉化為直接在陣列中從後往前「就地交換」，大幅降低了時間與空間成本。後來 Donald Knuth 在《The Art of Computer Programming》中詳細介紹了這個版本，因此演算法也被廣泛稱為 Knuth Shuffle。

今天無論是程式語言標準庫中的 shuffle 函式，或是線上隨機分組工具，大多數都採用這個現代版 Fisher-Yates 演算法。它之所以流傳超過半個世紀，正是因為其設計巧妙、實作簡單，而且能在 O(n) 時間內產生真正均勻分布的隨機排列。

Fisher-Yates Shuffle 的運作原理（逐步說明）

現代 Fisher-Yates Shuffle 的核心邏輯非常直覺：從陣列的尾端開始，每次選取一個尚未被洗過的元素與當前位置的元素交換，逐步完成一個完全隨機的排列。以下是具體步驟：

假設我們有一個 5 筆資料的陣列 [A, B, C, D, E]，索引從 0 到 4。

1. 從最後一個位置 i = 4 開始。
2. 產生一個範圍在 0 到 i（包含兩端）的隨機整數 j。
3. 將位置 i 與位置 j 的元素交換。
4. 將 i 減 1，重複步驟 2–3，直到 i = 0。

實際跑一遍可能長得像這樣：

• i=4 時，隨機選到 j=1，交換 E 與 B → 陣列變成 [A, E, C, D, B]
• i=3 時，隨機選到 j=3，自己換自己 → 陣列維持 [A, E, C, D, B]
• i=2 時，隨機選到 j=0，交換 C 與 A → 陣列變成 [C, E, A, D, B]
• i=1 時，隨機選到 j=0，交換 E 與 C → 陣列變成 [E, C, A, D, B]
• i=0 時結束，最終隨機排列為 [E, C, A, D, B]

關鍵在於，已經被交換過的後端元素不再參與後續的隨機選取，這確保了每一個元素在某個步驟中被選中的機率與其位置無關，同時也避免重複處理，達成線性時間的效率。

公平性證明：為何每個排列機率均等？

Fisher-Yates Shuffle 之所以被視為「公平」，是因為它能夠產生所有可能的排列（共 n! 種），而且每一種排列出現的機率完全相等，皆為 1/n!。

我們可以從最後一個位置來思考：在第一輪中，任何一個原始元素出現在最後一個位置（i=n-1）的機率都是 1/n，因為 j 是從 0 到 n-1 均勻隨機選取。接著，倒數第二個位置會從剩下的 n-1 個元素中隨機選取，任何一個剩餘元素成為該位置內容的機率都是 1/(n-1)。依此類推，整個序列生成的機率即為：

1/n 1/(n-1) 1/(n-2) … 1/1 = 1/n!

由於每個步驟的隨機選擇彼此獨立且均勻，最終排列的分佈必然是完全均勻的。這與依靠排序比較器加上隨機值的方法完全不同——那類方法因為排序演算法的內部不穩定性和比較器不符合傳遞律，往往會產生某些排列機率偏高或偏低的「偽隨機」結果。

簡而言之，如果你需要一個真正公平、無偏的隨機排列，Fisher-Yates Shuffle 是理論上最站得住腳的選擇，也是實務上最輕量的方案。

Fisher-Yates 的程式碼實作（簡化版）

雖然本文讀者包含教師與培訓師，不一定要會寫程式，但一個簡化的虛擬碼能夠幫助你更透徹理解這個演算法的邏輯。以下用類似 JavaScript 的語法呈現：

function fisherYatesShuffle(array) {
  // 從最後一個元素開始往前處理
  for (let i = array.length - 1; i > 0; i--) {
    // 隨機選取一個 0 到 i 之間的索引
    const j = Math.floor(Math.random() * (i + 1));
    // 將位置 i 和 j 的元素互換
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

這個函式直接在原陣列上修改，不需要額外的儲存空間，時間複雜度為 O(n)，空間複雜度僅 O(1)。任何以現代瀏覽器執行的線上工具，都可以非常流暢地用這段邏輯瞬間打亂數百甚至數千個項目。

若你使用 Python，標準庫中的 random.shuffle 函式也是採用 Fisher-Yates 演算法。可見其不僅是教科書範例，更是業界處理隨機排列時的預設選擇。

常見錯誤：Sort with random comparator 的陷阱

許多人在需要隨機排列時，會直覺地寫出類似以下的程式碼：

array.sort(() => Math.random() - 0.5);

這種方法看起來簡單，但卻存在嚴重缺陷。首先，sort 函式的前提是比較器必須滿足一致性（例如傳遞性），而隨機比較器每次回傳的值都不同，破壞了排序演算法的前提，可能導致效率降低，甚至在某些引擎中出現無法預期的行為。

更重要的是，這樣做出來的排列並不均勻。因為不同排序實作（如快速排序、合併排序）對於比較次數和順序的依賴，會使某些元素停留在原位的機率偏高，或某些排列樣式出現得更加頻繁。一項經典的分析顯示，對於長度為 5 的陣列，某些排列的出現機率可能比均勻分佈高出 50%，這在需要真正公平的場景（如課堂分組、隨機抽籤）中是不可接受的。

相比之下，Fisher-Yates Shuffle 每一步的機率都有嚴格的數學保證，且不需要依賴排序引擎的內部行為，是更可靠、更透明的選擇。

在實務上：Fisher-Yates 如何驅動隨機分組工具？

你可能會好奇：這個演算法和課堂上的隨機分組有什麼關係？答案是——幾乎所有可靠的隨機分組工具，背後都隱藏著 Fisher-Yates Shuffle。

當你在 隨機分組生成器 貼上一份學生名單並按下「生成分組」，系統會進行以下動作：

1. 將所有姓名讀入一個列表。
2. 使用 Fisher-Yates Shuffle 將整個列表徹底打亂。
3. 根據你指定的組數或每組人數，依序將打亂後的名單切分為各小組。

因為洗牌後的順序是完全隨機且均勻分佈的，所以每個學生被分配到任何一組的機會都相等，不會因為名單原先的排列順序（如按座號、筆畫）而產生偏袒。同樣的道理，隨機配對工具 也是先將所有人員打亂，再兩兩一組形成配對；而 隨機挑選學生 則是在洗牌後直接選取位於開頭的幾位，絕不會因為演算法而偏好特定同學。

如果你使用 Google Meet 或 Teams 進行即時互動，我們的工具也整合了視訊會議主持人操作列，讓你一鍵就能將公平打亂後的分組結果分享給所有參與者。這整段流程的核心，正是那短短幾行的 Fisher-Yates 邏輯。

常見問題 FAQ

Fisher-Yates Shuffle 和 Knuth Shuffle 是一樣的東西嗎？

是的，兩者指的是同一個演算法。Knuth Shuffle 這個名稱源自 Donald Knuth 在《The Art of Computer Programming》中對現代版 Fisher-Yates 演算法的詳細介紹與推廣，因此程式界常將 Fisher-Yates Shuffle 與 Knuth Shuffle 混用，它們的邏輯完全一致。

這個演算法真的適合用來做學生隨機分組嗎？

非常適合。Fisher-Yates Shuffle 提供的均勻隨機分佈，意味著每一個學生被排在任何位置的機率皆相等，後續切分小組時就能確保公平。無論是隨機分組、配對還是挑選，採用這個演算法都是教育現場最值得信賴的做法。

為什麼不直接用內建的排序加隨機數？

如同前面章節所述，排序加隨機數的方法既不能保證每個排列均勻出現，也可能因為比較器不穩定而產生難以預料的結果。在重視公平性的場合（如課堂表現、團隊任務分配），不建議使用這種「偽隨機」的捷徑。

Fisher-Yates Shuffle 可以處理多大量的名單？

由於其 O(n) 時間複雜度和 O(1) 空間複雜度，即使名單多達數千或上萬筆，現代裝置也能在數毫秒內完成。我們的線上工具經過最佳化，可以支援大型班級或全校性的活動分組。

如何讓分組的過程更透明、更被同學信任？

你可以直接使用一個公開信譽良好的工具，例如 **隨機分組生成器**，並在投影螢幕上即時展示洗牌與分組過程。因為演算法公平、不會記住歷史結果，每一次點擊都是獨立的隨機事件，同學自然能感受到程序上的公正。

立即體驗真正的隨機公平分組

理解 Fisher-Yates Shuffle 的原理後，你已經知道「隨機」背後並不簡單。想要將這個經典演算法應用在課堂、培訓或團隊活動中嗎？立刻試試我們的 **線上隨機分組工具**，只要貼上名單、選擇組數，系統就會在瞬間用公平洗牌的方式為你產生無偏的小組。無須註冊，完全免費。

讓每一次分組，都建立在科學與信任之上。