Fisher–Yates 洗牌演算法：均勻排列、隨機數與 JavaScript 陷阱

n 個可區分的項目共有 n! 種排列。3 個項目有 6 種，5 個有 120 種，10 個有 3,628,800 種；52 張不同的啤牌則有約 8.07 × 10⁶⁷ 種排列。即使兩個項目的值相同，分析時仍可按原來的位置區分。

均勻洗牌要求每種排列出現的概率都是 1/n!。每個項目落在各位置的概率相同，並不足夠。例如只以相同概率產生 ABC、BCA、CAB，三個項目的位置都平均分布，卻完全不會出現其餘三種排列。

Fisher–Yates 能達到均勻排列的前提，是每一步即使已知之前的選擇，仍能均勻選取交換位置。因此，隨機數來源和整數範圍轉換都必須一併考慮。

Ronald A. Fisher 和 Frank Yates 的 Statistical Tables for Biological, Agricultural and Medical Research 初版於 1938 年出版。參考資料中的大學館藏是1963 年第六版，並非 1938 年初版。

紙筆方法每次從餘下項目中均勻選取一個，將它移除，再依次寫到另一份列表。這種做法可用來隨機安排實驗次序或分配對象。

1. 列出原有項目。
2. 從餘下項目中均勻選取一個。
3. 把選中的項目加入輸出，並從原列表移除。
4. 重複操作，直至沒有剩餘項目。

無論使用隨機數表還是軟件，轉換至指定整數範圍時，都不能偏向某些選項。以下介紹如何將這個過程有效率地搬到陣列上。

Richard Durstenfeld 在 1964 年的 Algorithm 235: Random Permutation 中，描述了把隨機選中的項目交換到最後一個未確定位置的方法。若每次刪除項目都要將後面的陣列內容往前搬，簡單實作可花上 O(n²) 時間；交換則避免了這種反覆搬移。

讓 i 由 n−1 遞減至 1：
  從 [0, i] 均勻選取整數 j
  交換 arr[i] 與 arr[j]

j 必須從包括兩端的 0..i 選取，完成交換後便確定位置 i。與自己交換亦是必要選項。假設每次交換和取得隨機數都需常數時間，原地版本的時間複雜度為 O(n)，額外空間為 O(1)。原地操作並不等於完全不使用額外記憶體。

Knuth 在 The Art of Computer Programming 第二卷以 Algorithm P 討論此方法，因此也有 Knuth shuffle 之稱。這個名稱並不表示獲標準制定機構認證。

以 ABC 為例，第一次有 3 個交換位置可選，第二次有 2 個。每一步均勻選擇時，下列每條路徑的概率都是 1/6。

一般而言，指定最終排列後，便可由最後一個位置開始，依次唯一確定每次要選哪個項目。選擇路徑與排列有一對一對應，故每個排列的概率為 1/n × 1/(n−1) × … × 1/2 = 1/n!。只數出 n! 條路徑並不足以完成證明，還要確認這個一對一關係。

條件是即使已知之前的選擇，每一步仍以相同概率選到0..i 的所有整數。空陣列和只有一個項目的陣列各只有一種排列，毋須交換。

以下寫法不能用來保證均勻洗牌：

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

比較函數須對相同輸入給出一致結果，並符合反身性、傳遞性等要求。隨機比較破壞了這些條件。ECMAScript 對不一致比較函數所得的排序，規定為由實作決定；亦沒有保證比較次數一定是 O(n log n)，或採用特定排序演算法。

實際偏差會隨引擎、版本及輸入而變，不能說所有輸入都必定出現同一種偏差。但無法保證均勻性，已足以令它不適合作公平抽選用途。另外，sort 會修改原陣列。

另一個常見的直覺寫法，是每次從整個陣列選交換對象：

for (let i = 0; i < n; i++) {
  const j = Math.floor(Math.random() * n);
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

n=3 時，即使假設每次整數選擇均勻，也有 3³=27 條路徑分配給 6 種排列，無法平均分配。完整列舉後，每種排列出現 4 次或 5 次。不過，不能把這個結論延伸為 n=0 或 1 等簡單情況也必定有偏差。

遞減版本的 i 由 n−1 到 1，j 從 0..i 選取。遞增版本的 i 由 0 到 n−2，j 則從 i..n−1 選取。不能只反轉迴圈方向而保持原有範圍。

若遞減版本排除 i 本身，只選 0..i−1，就會變成 Sattolo 類型的單一循環生成方法。它的用途與產生所有排列不同，不能代替容許項目留在原位的均勻洗牌。

將均勻的 32 位元無符號整數 r 除以 n 取餘數，若 2³² 不能被 n 整除，便會產生取餘數偏差（modulo bias）。設 2³² = qn + k，餘數 0..k−1 各有 q+1 個原值對應，其餘餘數則各有 q 個。

n=7 時，q=613,566,756、k=4，兩類結果的概率差為 1/2³²。n=2³¹ 時沒有這種偏差，但 n=2³¹+1 時，部分結果的概率是其他結果的兩倍。偏差並非隨 n 增大而單調增加。

拒絕採樣（rejection sampling）會捨棄大於或等於 limit = floor(2³²/n) × n 的值，再對接受的值取餘數。接受範圍的大小是 n 的倍數，故每個餘數對應相同數量的原值。n=7 時捨棄最後 4 個值。

以下範例可在瀏覽器執行，適用於沒有空洞的一般陣列。它建立淺層複本，不改動原陣列，但不會複製項目所指向的物件。如 Web Crypto 不可用或操作拋出例外，便回報失敗，不會退回使用 Math.random。

function unbiasedRandomInt(n) {
  const range = 2 ** 32;
  if (!Number.isInteger(n) || n < 1 || n > range) {
    throw new RangeError("請輸入介乎 1 至 2^32 的整數");
  }
  const source = globalThis.crypto;
  if (!source || typeof source.getRandomValues !== "function") {
    throw new Error("無法使用 Web Crypto");
  }
  const limit = Math.floor(range / n) * n;
  const value = new Uint32Array(1);
  for (let attempt = 0; attempt < 128; attempt++) {
    source.getRandomValues(value);
    if (value[0] < limit) return value[0] % n;
  }
  throw new Error("隨機採樣未能完成");
}

function shuffledCopy(items) {
  if (!Array.isArray(items)) throw new TypeError("請提供陣列");
  const result = [...items];
  for (let i = result.length - 1; i > 0; i--) {
    const j = unbiasedRandomInt(i + 1);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

console.log(shuffledCopy(["A", "B", "C"]));

交換部分需要 O(n) 時間，陣列複本需要 O(n) 空間。每次整數選擇最多嘗試 128 次，仍未成功便終止。在 32 位元值獨立且均勻的模型下，每次接受概率大於 1/2，連續拒絕 128 次的概率小於 2⁻¹²⁸。上限是為了避免異常時無限迴圈，並不限制 Web Crypto 內部操作的時間。中途失敗不會傳回部分完成的陣列。

Math.random 產生大於或等於 0、少於 1、近似均勻分布的值，但具體方法及離散值的構成由 ECMAScript 實作決定。它不保證密碼學用途所需的不可預測性，也不能直接宣稱浮點數轉換後的整數嚴格均勻。Web Crypto 可填入整數型別陣列；這個範例用 Uint32Array 取得 32 位元值，並不代表 API 只處理 32 位元。Node.js 的 crypto.randomInt(0, i + 1) 提供避免取餘數偏差的整數選取方式。

應區分 API 的規格要求和某個版本的內部演算法。以下 API 提供重新排列功能，但預設隨機數來源未必適合密碼學用途。

仍在提案階段的功能，不能當成現行標準 API。應按用途考慮均勻性、不可預測性，以及是否需要可重現結果的種子（seed）。有限週期的偽隨機數產生器亦有局限：陣列足夠長時，便無法產生所有排列。

以下介紹的是 NanToo 日文版工具。

隨機數來源、整數範圍轉換及陣列排列是三個需要分別驗證的環節。抽籤工具把 Web Crypto 的 32 位元值經拒絕採樣轉成交換位置，再以 Fisher–Yates 排列。骰仔、輪盤及密碼產生器則直接選取點數、候選項目或字元。單憑演算法名稱，不能聲稱公平性已經第三方審核，亦不能保證整個使用情境的安全。

另可參閱密碼強度與熵的介紹，了解隨機選取與實際安全需求之間的分別。

• 所有排列等概率，並不等於各項目的位置分布平均。
• 遞減 Fisher–Yates 要在已知之前選擇的情況下，仍從 0..i 均勻選取交換位置。
• 隨機 sort 比較、每次與整個範圍交換、排除 i 本身，都不能代替均勻產生所有排列的方法。
• 拒絕採樣可把均勻整數轉成指定範圍，但亦要設計輸入驗證及異常時的終止方式。
• 均勻性和不可預測性是不同性質，選對演算法不等於符合公開抽獎的審核要求。

從洗好的牌堆抽牌而不放回，並非獨立試驗。例如從 52 張牌抽 2 張，兩張都是 A 的概率是 4/52 × 3/51 = 1/221。抽出第一張後，餘下的牌數已改變。

如果每次以固定概率 p 獨立成功，成功次數便可用二項分布描述。p=0.03 時，獨立抽選 33 次至少成功一次的概率為 1−0.97³³ ≈ 63.4%。若設有保底或概率會隨次數改變，就不能直接套用同一公式。計算前，應先分清放回抽樣、不放回抽樣，以及額外的保底規則。