· 開発

sort(() => Math.random() - 0.5) でシャッフルしてはいけない理由と Fisher–Yates

ランダムな比較関数で配列を並べ替えても均等に混ざらない理由を ECMAScript 仕様で確認し、すべての順列が同じ確率で出る Fisher–Yates シャッフルと、乱数の範囲・生成器の注意点をまとめました。

開発アルゴリズム

配列をランダムに並べ替える方法を調べると、次の1行をよく見かけます。

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

短くて正しそうに見えますが、均等には混ざりません。['A', 'B', 'C'] をこの方法で60万回シャッフルし、並び順ごとの割合を数えた結果です。

並び順 割合
ABC 37.4%
ACB 6.2%
BAC 12.5%
BCA 6.3%
CAB 6.3%
CBA 31.3%

均等なら6通りすべてが約16.7%になるはずです。上の数値は Node.js v24.13.0 で観察した結果で、別のエンジンやバージョンでは分布が変わる可能性があります。変わりうること自体が問題です。

仕様はこの使い方を保証していない

ECMAScript の仕様は、sort の並び順の保証を、比較関数が「一貫した比較関数（consistent comparator）」であることを前提に定めています。一貫した比較関数の条件の1つ目は、同じ2つの値 a, b で呼べば常に同じ値を返すことです。Math.random() - 0.5 は同じ組で呼び直すと別の値、ときには別の符号を返しうるので、この条件を満たしません。その場合、仕様はソート順が実装定義（implementation-defined）になるとしか書いていません。結果の分布はエンジンのソートアルゴリズムがどの組を何回比較するかで決まり、均等になる保証はどこにもありません。

どこでも入れ替える方法も偏る

ソートを使わずに自分で書くシャッフルにも、よくある誤りがあります。各位置 i で、配列全体から選んだ位置 j と入れ替える方法です。

// 偏る方法
for (let i = 0; i < a.length; i++) {
  const j = Math.floor(Math.random() * a.length);
  [a[i], a[j]] = [a[j], a[i]];
}

要素が3つなら選び方は 3 × 3 × 3 = 27 通りで、順列は6通りです。27 は 6 で割り切れないので、すべての順列が同じ回数出ることはありえません。27通りをすべてたどると、ABC・CAB・CBA が4回、ACB・BAC・BCA が5回になります。一般に n が3以上なら n と n−1 は互いに素なので、n^n は n−1 で割り切れず、したがって n! でも割り切れません。要素が3つ以上あれば、この方法は必ず偏ります。

Fisher–Yates：まだ確定していない位置からだけ選ぶ

均等に混ぜるには、後ろから1つずつ位置を確定させます。位置 i では 0 から i まで、つまりまだ確定していない位置から1つ選んで入れ替えます。

function shuffle(items) {
  const a = [...items];
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1)); // 0 ≤ j ≤ i
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

選び方は n × (n−1) × … × 2 = n! 通りで、各順列はちょうど1通りの選び方からだけ生まれます。そのため j が範囲内で一様に選ばれるなら、すべての順列の確率は 1/n! で等しくなります。ループは n−1 回なので O(n) です。

標準ライブラリにも同じ構造があります。Java の Collections.shuffle のドキュメントは、リストを最後の要素から2番目の要素まで逆向きにたどり、先頭から現在位置までの範囲で選んだ要素を現在位置に入れ替えると説明しています。CPython の random.shuffle と Go の math/rand/v2 の Shuffle もソースコードを見ると同じループで、Go のソースのコメントには Fisher–Yates という名前が書かれています。

アルゴリズムが正しくても乱数が問題になる

Fisher–Yates が均等な結果を出すのは、j が一様に選ばれることが前提です。

  • 範囲。 Math.floor(Math.random() * (i + 1)) は0以上 i+1 未満の整数を返します。MDN の getRandomInt の例と同じ範囲です。i + 1 の代わりに i を使うと j が i になれません。最後の位置には必ず別の要素が入るため、元の並びのままの結果など一部の順列がまったく出なくなります。
  • 剰余による偏り。 32ビットの整数乱数を % n で縮めると、2^32 が n で割り切れないときに小さい値が少し出やすくなります。2^32 を 6 で割った余りは 4 なので、0〜3 は 4〜5 より1つずつ多く対応します。これを避けるには、% n を取る前に floor(2^32 / n) × n 以上の値を捨てて引き直します。残る値の個数が n の倍数になり、0 から n−1 までが同じ回数ずつ対応します。CPython の _randbelow も引き直しを使っていて、必要なビット数だけ引いた値が n 以上なら引き直します。
  • セキュリティ。 MDN は Math.random() が暗号論的に安全な乱数を提供しないとして、セキュリティに関わる用途には crypto.getRandomValues() を使うよう案内しています。Python のドキュメントも、セキュリティ用途には random ではなく secrets モジュールを勧めています。結果を予測されると困る抽選なら、まず生成器を替えるべきです。
  • 生成器の周期。 Python のドキュメントは、長さが少し増えるだけで順列の数はほとんどの乱数生成器の周期を超え、長いシーケンスの順列の大半は生成されえないと書いています。メルセンヌ・ツイスタ（周期 2^19937−1）の周期にすべての順列が収まる最大の長さは 2080 です。Java のドキュメントが “approximately equal likelihood” と書くのもまさにこのためで、既定の乱数源は偏りのない独立したビット源に近いだけだと説明されています。

いくつかだけ選ぶとき

n 個から k 個だけ必要なら（0 ≤ k < n）、ループを k 回で止めて構いません。後ろから混ぜた場合、最後の k 個がランダムな標本になります。k が n なら上の関数どおり n−1 回回します。Python なら random.sample(population, k) が元のシーケンスを変えずに、非復元抽出で k 個を選び、選ばれた順に返します。元のシーケンスに同じ値が複数あれば、結果にも同じ値が複数回出ることがあります。

このサイトのくじ引き・チーム分け・順番決めも Fisher–Yates で並べ替えています。j は crypto.getRandomValues() で得た32ビット値のうち floor(2^32 / n) × n 以上のものを捨てて引き直す方法で選んでいます。

ブログへ