Fisher-Yates シャッフル — くじ引きで偏りを避ける並び替えアルゴリズム

区別できる n 個の要素の並び順は n! 通りです。3個なら6通り、5個なら120通り、10個なら3,628,800通り、52枚の異なるカードなら約8.07 × 10⁶⁷通りあります。同じ値を持つ要素も、ここでは元の位置で区別します。

一様なシャッフルとは、すべての順列が1/n!の確率で現れることです。各要素の位置だけが均等でも十分ではありません。例えばABC・BCA・CABだけを等確率で返す方法は、各要素の位置が均等でも6順列の半分を生成できません。

Fisher–Yatesは、各段階で過去の選択を条件としても交換位置を一様に選べるとき、この条件を満たします。乱数源と範囲への変換も正しさの一部です。

Ronald A. FisherとFrank YatesのStatistical Tables for Biological, Agricultural and Medical Researchは1938年に初版が出版されました。参考文献に挙げた大学所蔵の第6版は1963年で、1938年の版と区別する必要があります。

紙上での方法は、残っている要素から1つを一様に選び、取り除いて別の列へ順に書き出すものです。実験で対象の順番や割り当てを無作為化する考え方につながります。

1. 元の要素を一覧にする
2. 残りの要素から1つを一様に選ぶ
3. 選んだ要素を出力し、残りの一覧から除く
4. 要素がなくなるまで繰り返す

乱数表などで範囲内の整数を選ぶときも、特定の候補を多く選ぶ変換をしてはいけません。以下では、この手作業を配列上で効率よく行う方法を扱います。

Richard Durstenfeldの1964年の論文Algorithm 235: Random Permutationは、末尾の未確定位置とランダムな位置を交換する方法を示しました。要素を削除するたびに配列を詰める単純な実装はO(n²)ですが、交換なら線形時間で処理できます。

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

両端を含む0..iから交換相手を選び、位置iを確定させます。自分自身との交換も必要な選択肢です。各交換と乱数取得を定数時間とすればO(n)、その場で配列を書き換える版の追加領域はO(1)です。「追加メモリを一切使わない」という意味ではありません。

KnuthのThe Art of Computer Programming第2巻でもAlgorithm Pとして扱われ、Knuth shuffleとも呼ばれます。これは標準化団体による規格制定を意味しません。

ABCを例にすると、最初の交換相手は3通り、その次は2通りです。各選択を一様に行うと、次の6経路はそれぞれ1/6の確率になります。

一般にも、特定の最終順列を決めると、末尾に置く要素、その次に置く要素という順に交換相手が一意に定まります。選択経路と順列は1対1なので、確率は1/n × 1/(n−1) × … × 1/2 = 1/n!です。経路数がn!というだけでなく、この1対1対応が証明に必要です。

条件は、各段階で過去の選択を条件としても0..iの全整数を等確率で選ぶことです。空配列と1要素の配列は、そのまま返す1通りしかありません。

次の方法を一様なシャッフルとして使ってはいけません。

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で割り切れない限り偏りが生じます。2³² = qn + kとすると、0..k−1にはq+1個、残りにはq個の元の値が対応します。

n=7ならq=613,566,756、k=4です。確率の絶対差は1/2³²です。n=2³¹では偏りがなく、n=2³¹+1では一部の値の確率が他の2倍になります。偏りはnの大きさに対して単調には増えません。

棄却サンプリングでは、limit = floor(2³²/n) × n以上を捨て、残りをnで割ります。受理範囲はnの倍数なので、各余りに同数の値が対応します。n=7では末尾4値を捨てます。

次はブラウザ向けの実行例です。密な通常配列を浅くコピーし、元配列を変更しません。要素のオブジェクト自体は複製しません。Cryptoが使えない場合や例外時は失敗し、Math.randomへ切り替えません。

function unbiasedRandomInt(n) {
  const range = 2 ** 32;
  if (!Number.isInteger(n) || n < 1 || n > range) {
    throw new RangeError("Expected an integer from 1 to 2^32");
  }
  const source = globalThis.crypto;
  if (!source || typeof source.getRandomValues !== "function") {
    throw new Error("Web Crypto is unavailable");
  }
  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("Random sampling did not complete");
}

function shuffledCopy(items) {
  if (!Array.isArray(items)) throw new TypeError("Expected an array");
  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)です。1回の整数選択は最大128回で失敗させます。独立一様な32ビット値というモデルでは1回の受理率は1/2より大きく、128回連続棄却の確率は2⁻¹²⁸未満です。この上限は異常時の無限ループを避けるためで、Web Cryptoの内部処理時間を制限するものではありません。途中で失敗した配列は返しません。

Math.randomは0以上1未満のおおむね一様な値ですが、具体的な方式と離散値の構成はECMAScriptでは実装依存です。暗号用途の予測困難性を保証せず、浮動小数値からの範囲変換を厳密一様とも断言できません。Web Cryptoは整数型の配列を埋めるAPIで、上例ではUint32Arrayを使って32ビット値を得ます。API自体が常に32ビット値だけを扱うわけではありません。Node.jsではcrypto.randomInt(0, i + 1)がモジュロバイアスを避ける整数選択を提供します。

言語のAPI契約と、特定バージョンの内部アルゴリズムを分けて考えます。次のAPIは配列などの並べ替えを提供しますが、既定の乱数源が暗号学的に安全とは限りません。

提案中の機能を現在の標準APIとして紹介してはいけません。シャッフルの一様性、乱数の予測困難性、再現可能なseedの必要性を用途に応じて選びます。有限周期の疑似乱数生成器では、配列が十分に長いとすべての順列に到達できないという制約もあります。

乱数源、整数範囲への割り当て、配列の並べ替えは別々に検証する必要があります。くじ引きでは Web Crypto API の32ビット値を棄却サンプリングで交換位置へ割り当て、Fisher-Yates で並べ替えます。サイコロ、ルーレット、パスワード生成は配列を並べ替えず、同APIの値を棄却サンプリングで面・候補・候補文字へ割り当てます。アルゴリズム名だけで第三者監査済みの公平性や、利用先を含む安全性を保証するものではありません。

Mersenne Twister 記事 と合わせて、「乱数生成」と「乱数による並び替え」は別の問題で、それぞれの前提と役割を把握しておくと、実装の品質が上がります。

• すべての順列が等確率であることと、各要素の位置だけが均等であることは別です。
• 降順Fisher–Yatesは、過去の選択を条件としても交換位置を0..iから一様に選ぶ必要があります。
• sortの乱数比較、全範囲との交換、i自身の除外は、一様な全順列生成の代わりになりません。
• 一様な整数源からの範囲変換には棄却サンプリングを使えます。入力範囲と異常時の終了も設計します。
• 一様性と予測困難性は別の性質です。アルゴリズムだけで公的な抽選の監査要件を満たすわけではありません。

シャッフル後の山札から戻さずに引く結果は独立試行ではありません。例えば52枚から2枚を引いて両方がエースである確率は、4/52 × 3/51 = 1/221です。1枚目の後に残り枚数が変わります。

一方、毎回同じ確率pで独立に成功する抽選の成功回数は二項分布で扱えます。p=0.03の独立な33回で1回以上成功する確率は1−0.97³³ ≈ 63.4%です。天井や確率変動があれば同じ式をそのまま使えません。

• ガチャ確率計算機 — 独立抽選と天井条件を区別
• ダイス確率計算機 — 独立なダイスの合計分布を畳み込みで計算
• ガチャ確率の数学 — 復元抽出と非復元抽出を混同しないための関連テーマ