Fisher-Yates シャッフル — くじ引き・ルーレットを支える 1938 年生まれの「公平な並び替え」アルゴリズム

n 個の要素を持つ配列を「ランダム」に並び替えたい — 直感的には簡単そうですが、本当に均等な分布を実現するのは案外難しい。

n 個の並び順は n! (階乗) 通りあります。例えば:

• n = 3: 6 通り
• n = 5: 120 通り
• n = 10: 約 363 万通り
• n = 52 (トランプ 1 デッキ): 約 8.07 × 10⁶⁷ 通り — 宇宙にある原子数より多い

「公平なシャッフル」とは、n! 通りの並び順それぞれが 1/n! の確率で現れること。各要素がどの位置に来る確率も均等になっている必要があります。

これを実現するアルゴリズムが Fisher-Yates です。

1938 年、英国ケンブリッジ大学の統計学者 Ronald A. Fisher と Frank Yates は、農業・生物学・医学研究の実験設計向けに "Statistical Tables for Biological, Agricultural and Medical Research" 第 6 版を出版。この中に「乱数で並び替える方法」として現代の Fisher-Yates シャッフルの原型が記載されました。

原典のアルゴリズム (鉛筆と紙の手作業向け):

1. 1〜N の数字を紙に書く
2. ランダムに 1〜N の中から 1 つ選び、抹消して別の場所に書き写す (これが 1 番目)
3. 残った N-1 個から 1 つ選び、抹消して書き写す (これが 2 番目)
4. ...全部書き終わるまで繰り返す

これは農業圃場での「区画の処理割り当てを完全にランダム化する」用途を想定したもので、Fisher の有名な「ランダム化比較試験」(現代の臨床試験の基礎) に直結する考案でした。

当時はコンピュータがないので、乱数は別途用意した「乱数表」を引いて使用。原典では Tippett (1927) の乱数表を参照しています。

1964 年、Richard Durstenfeld は ACM Communications に "Algorithm 235: Random Permutation" を発表。Fisher-Yates のアイデアを、コンピュータ向けに O(n) で in-place (追加メモリ不要) に実装する手法を示しました。

原版 Fisher-Yates は「選んで抹消、書き写し」が必要で、ナイーブ実装すると O(n²)。Durstenfeld は「最後尾から swap で組み立てる」という発想で線形時間化:

// Durstenfeld 1964 (現代の標準実装)
for i = n-1 down to 1:
  j = random integer in [0, i]
  swap(arr[i], arr[j])

これだけ。3 行のループで完璧にシャッフルできます。各ステップで「まだ確定していない区間 [0, i] の中からランダムに 1 つ選んで末尾と swap」する。

Knuth は 1969 年の The Art of Computer Programming, Vol. 2, §3.4.2 でこのアルゴリズムを「Algorithm P (Permutation)」として体系化。以後、業界では「Knuth shuffle」とも呼ばれるようになりました (実質 Fisher-Yates と同じ)。

Fisher-Yates シャッフルが「n! 通りすべて等確率」を実現する証明:

n = 3 の場合で考える。3 要素 [A, B, C] を並び替える。

// 初期: [A, B, C]

// i=2: random in [0, 2] → 3通り
//   j=0: swap(arr[2], arr[0]) → [C, B, A]   確率 1/3
//   j=1: swap(arr[2], arr[1]) → [A, C, B]   確率 1/3
//   j=2: swap(arr[2], arr[2]) → [A, B, C]   確率 1/3

// i=1: random in [0, 1] → 2通り
// 上記 3 ケースそれぞれで さらに 2 通りに分岐

// 合計 6 ケース、各 1/6 の確率
// → n! = 6 通りの並びがそれぞれ 1/6 で出現

各ステップ i での選択肢が i+1 通りで、すべて独立だから合計 n × (n-1) × ... × 1 = n! 通りが等確率に出現する、というのが数学的なポイント。

重要な条件: random in [0, i] (両端含む)。これを [0, i-1] (i 含まず) や [0, n-1] (常に全範囲) にすると分布が偏る。次の章でその落とし穴を見ます。

JavaScript で配列をシャッフルするとき、よく見かけるコード:

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

一見もっともらしいですが、これは均等分布になりません。理由:

• JavaScript の Array.prototype.sort() はエンジンによって異なる実装 (V8 は TimSort、SpiderMonkey は別実装)
• sort は「比較が一貫している」前提の計算量最適化を行う — compareFn が乱数だと前提が崩れる
• ECMAScript 仕様上、sort 中の比較回数が O(n log n) 程度になるが、実際の swap 回数は要素配置に依存

2018 年に Mike Bostock や Cristian Vasile が実証したところ、Chrome v70 (V8) で [1,2,3] を 100 万回シャッフルすると、一部の並びが 18% 出る一方、別の並びは 14% — 約 30% の偏差が生じる結果に。完全な乱数なら各並び 16.67% (1/6) が期待値。

結論: arr.sort(() => Math.random() - 0.5) は実は乱数並び替えとして機能しない。カジュアル用途で気にならないかもしれませんが、抽選・ゲーム・統計サンプリング等で使うと結果が偏ります。

もう 1 つよくある間違い:

// ナイーブシャッフル (間違い!)
for (let i = 0; i < n; i++) {
  const j = Math.floor(Math.random() * n);  // ← 0 から n-1 全範囲
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

ループは正しい回数 (n)、swap も正しい — でも分布が偏ります。

分析: 上記は n^n 通りの組み合わせが生じるが、求める n! の倍数にならない。例えば n=3 なら 27 通りの組み合わせ → 6 通りの並びにマッピングされるが、各並びの出現回数は 4-5 回となり等しくない。

正解: ループ範囲を「i から n-1」に限定:

// Fisher-Yates 正解版
for (let i = n - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));  // 0..i の範囲のみ
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

差分は 2 箇所:

• ループは n-1 から 1 へ (逆順、または 0 から n-2 へ昇順でも可)
• j の範囲は 0..i (i 含む) に限定

この 2 行の調整で、n! 通り均等分布が実現されます。

乱数生成器 (RNG) が 32-bit 整数 (0 〜 2³² - 1) を返すとき、これを「0..n-1 の範囲に縮める」処理に注意が必要です。

// 偏る実装
const j = randomInt32() % n;

なぜ偏るか: 2³² (≈ 4.3 × 10⁹) を n で割ると、n が 2³² の約数でない限り、「余り」が均等にならない。例えば n = 7 だと、2³² mod 7 = 4 で、0..3 の出現確率が 4..6 より約 14% 多くなる。

正しい実装は棄却サンプリング (rejection sampling):

// 正しい: 範囲外を棄却して再抽選
function unbiasedRandomInt(n) {
  const max = Math.floor(2**32 / n) * n;
  let r;
  do {
    r = randomInt32();
  } while (r >= max);
  return r % n;
}

n = 52 (トランプデッキ) のような小さな範囲では % n でも実用上問題ない (偏りが 10⁻⁸ レベル) ことが多いですが、暗号用途や厳密な統計サンプリングでは棄却サンプリングが必要です。

JavaScript の Math.random() は [0, 1) の実数を返すため、Math.floor(Math.random() * n) は形式上モジュロバイアスがありますが、2⁵² (倍精度浮動小数の精度) と n の比なので n が天文学的に大きくない限り無視可能。

一方、Web Crypto API の crypto.getRandomValues() は 32-bit 整数を返すため、% 演算は注意が必要 — Node.js の crypto.randomInt(min, max) は内部で棄却サンプリングを行う実装になっています。

言語/環境	シャッフル関数	実装
Python	random.shuffle(list)	Fisher-Yates (in-place)
Java	Collections.shuffle(list)	Fisher-Yates
Ruby	arr.shuffle	Fisher-Yates
PHP	shuffle($arr)	Fisher-Yates
Go	rand.Shuffle(n, swap)	Fisher-Yates
Rust	rand::seq::SliceRandom::shuffle	Fisher-Yates
C++	std::shuffle (C++11+)	Fisher-Yates
JavaScript	標準なし	自前実装 or Lodash _.shuffle

主要言語の標準ライブラリは Fisher-Yates を提供しています。JavaScript だけが標準にシャッフル関数を持たないので、自前実装か Lodash 等を使う必要があります — そのため誤実装が広まりやすい。

ECMAScript には Array.prototype.shuffle のプロポーザルがありますが、2026 年現在 Stage 1 で停滞中です。

ツール	シャッフル必要性	実装
くじ引き	当選順序の決定	Fisher-Yates + Math.random()
ルーレット	セクター順序の事前混合	Fisher-Yates
サイコロ	不要 (各ロール独立)	Math.random() のみ
パスワード生成	文字種を均等選択	Fisher-Yates + crypto.getRandomValues()

くじ引きやルーレットでは Math.random() で十分、パスワード生成では暗号品質が必要なため crypto.getRandomValues() を使用。乱数源は違っても、シャッフルアルゴリズムは Fisher-Yates で統一されています。

昨日の Mersenne Twister 記事 と合わせて、「乱数生成」と「乱数による並び替え」は別の問題で、それぞれに正解アルゴリズムがあることを把握しておくと、実装の品質が上がります。

• Fisher-Yates シャッフル (1938) は 88 年使われ続ける標準アルゴリズム
• Durstenfeld 1964 で O(n) in-place 化、Knuth 1969 で TAOCP に体系化
• 核は 3 行: for i = n-1..1: j = random[0,i]; swap(arr[i], arr[j])
• arr.sort(() => Math.random() - 0.5) は偏る — 使用厳禁
• j の範囲を [0, n-1] にすると偏る — 必ず [0, i] に限定
• 32-bit 整数を % で範囲縮小するときはモジュロバイアスに注意 (棄却サンプリングを使う)
• Python/Java/Ruby/Go 等は標準ライブラリで提供、JavaScript だけは自前実装 (or Lodash)