手軽屋
ツール一覧

Fisher-Yatesシャッフルの仕組み

本ツールが採用しているシャッフルアルゴリズムが「公平」と言える根拠を、計算量と確率の観点から見ていきます。

参照した一次情報

アルゴリズムの概要

Fisher-Yatesシャッフルは、配列の末尾から先頭に向けて反復し、各ステップで「自分以下のインデックスからランダムに1つ選び、その要素と現在の位置を交換する」操作を繰り返します。 1938年にFisherとYatesが乱数表で手計算するために発表した手法を、1964年DurstenfeldがコンピュータでO(n)時間に改良した版を「Modern Fisher–Yates」と呼びます。本ツールもこの方式を採用しています。

擬似コードで書くと次の通りです。

for i from n−1 downto 1 do
    j ← random integer such that 0 ≤ j ≤ i
    exchange a[j] and a[i]

なぜ「等確率」が保証されるのか

配列の長さがnなら、可能な並び（順列）はn!通りです。Fisher-Yatesは各ステップで {0, 1, ..., i} から一つランダムに選ぶので、選び方の総数は n × (n−1) × ... × 1 = n! 通り。 各選択は独立かつ等確率なので、最終的な並びもn!通りそれぞれが 1/n! の確率で出現します。

これは数学的に証明されており、Wikipediaも「each permutation of the input has equal probability」と明記しています。 つまり「ある人だけ当選しやすい・順番が早くなりやすい」という偏りは原理的に存在しません。

よくある実装ミス：単純なswap

初学者が書きがちな「全インデックスからランダムに1つ選んで現在位置とswap」する素朴な実装は、確率分布に偏りが生じます。 長さnの配列に対して n回のランダム選択を行うと、選び方の総数は n^n となり、n!の倍数になりません。そのため一部の並びが他より高い確率で出現します。

// 偏りのある実装（やってはいけない）
for i from 0 to n−1 do
    j ← random integer such that 0 ≤ j ≤ n−1  // ←nではなくiまでが正解
    exchange a[j] and a[i]

Wikipediaはこの実装ミスを「naive shuffle」と呼び、可能性のあるn^n通りがn!で割り切れないため等確率にならないことを実証しています。 本ツールはこの罠を避け、必ず「自分以下のインデックスから選ぶ」Modern Fisher-Yates方式を実装しています。

計算量と実用性

3人の例で動きを追ってみる

[A, B, C] をシャッフルする例。配列の末尾（インデックス2）から開始します。

  1. i=2のとき、{0, 1, 2} から乱数で1つ選ぶ。仮にj=0なら A と C を交換 → [C, B, A]
  2. i=1のとき、{0, 1} から乱数で1つ選ぶ。仮にj=1なら B と B を交換 → [C, B, A]
  3. i=0で終了。結果は [C, B, A]

選び方は 3 × 2 × 1 = 6通り、起こりうる並びも3! = 6通りで一致するため、どの並びも1/6の確率で出現します。 この対応関係が「Fisher-Yatesは等確率」の数学的根拠です。

本ツールでの位置づけ

本ツールは Modern Fisher-Yates（Durstenfeld版）を crypto.getRandomValues() の暗号学的乱数と組み合わせて実装しています。 これにより「アルゴリズム的にも乱数源としても偏りがない」二重の公平性を実現しています。

応募者2名の単純なじゃんけんから1000名の懸賞当選者選びまで、同じアルゴリズムでO(n)で実行できるため、人数を増やしても結果は瞬時に表示されます。

関連ツール・記事