【完全解説】シャッフルアルゴリズムの決定版 Fisher–Yates

はじめに

ランダムシャッフルを実装するとき、多くの人がまず思いつくのは次のような書き方です：

const numbers = [1, 2, 3, 4, 5];
numbers.sort(() => Math.random() - 0.5);
console.log(numbers);

しかし、これは完全なランダムシャッフルではありません。 この方法ではバイアスが発生し、すべての並び順が同じ確率とはならないことが知られています。

そこで登場するのが Fisher–Yates シャッフル。ゲーム開発、統計処理、プロダクションコード、アルゴリズム教材など、広く使われてきた「正しい」シャッフルアルゴリズムです。

ソースコード

15パズルゲーム

トランプ神経衰弱ゲーム

🎯 Fisher–Yates シャッフルとは？

Fisher–Yates シャッフルは、配列を 計算量 O(n) で 完全公平 (uniform) にシャッフルできるアルゴリズムです。

特徴として：

• 配列のすべての順列（n! 通り）が 等しい確率 (1/n!) で生成される。
• インプレース (元の配列を書き換え) でも、コピーして使うイミュータブル方式でも実装可能。
• シンプルかつ高速で、バイアスがない。スタンダードな読み替えソート + ランダム並び替えより信頼性が高い。

✨ TypeScript での実装例（最も一般的な書き方）

function shuffle<T>(array: T[]): T[] {
  const result = [...array];
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

const numbers = [1, 2, 3, 4, 5, 6];
const shuffledNumbers = shuffle(numbers);
console.log(shuffledNumbers);

実装のポイント

部分	意味
i = length - 1 から逆順にループ	配列の後ろから順に「未決定要素」を選ぶ
j = random(0〜i)	未処理部分 (0〜i) からランダムに選ぶ
要素を入れ替える (swap)	選ばれた要素を「確定位置」に置く

このように、「末尾から順にランダムに選んで確定させる」ことで、すべての要素が等確率で任意の位置に入るようになります。

❌ よくある間違った書き方（やってはいけない）

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

なぜこの方法はダメか？

• sort() は比較関数に期待される性質（反射性、推移性など）を満たさず、不正な結果をもたらす可能性がある。
• 比較関数がランダムな値を返すことで、一見ランダムに見えても、すべての順列が等確率とはならない。大きな配列では偏りが顕著になる。
• 統計的にも「random sort」は不正確とされており、運用コードで使うべきではない。

実際、「見た目ランダムだけど均等ではない」シャッフルになりがちです。
読み込むと「なんとなくバラバラ」ですが、ある特定の並びが他の並びより出やすくなってしまう — これは非常に危険です。

🧠 なぜ Fisher–Yates は公平なのか？（直感と数学的背景）

🎩 直感的な説明 (「帽子とくじ引き」モデル)

• 配列を「まだ選ばれていない要素の集合 (帽子)」と、「シャッフル後に確定した要素 (ライン)」に分けて考える。
• 毎回、帽子からランダムに 1 つくじを引き (インデックス j を選ぶ)、その要素をラインに移す (swap)
• これを最後まで繰り返す → 帽子からの「無作為抽出 without replacement (重複なし抽出)」と同義になる

このモデルでは、最終的な並び順は「帽子から無作為抽出した順番」であり、すべての順列が同等に起こりうる。

📐 数学的な正しさ

• 各ステップで i 番目に処理する要素が 残りの未確定要素の中から均等に選ばれる
• その結果、各要素が任意の位置に入る確率が 1/n（あるいは等しい）になる。特に、最終的な並びは n! 通りすべてが等確率 1/n! で生成される。
• 結果として「均等かつ全組合せをカバーするランダムな順列」が得られる。

この性質により、Fisher–Yates は「真のランダムシャッフル」と言えるわけです。

🧪 イミュータブル版 / ミュータブル版 — 使い分け

🔄 ミュータブル (元の配列を書き換える)

function shuffleInPlace<T>(arr: T[]): void {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

const numbers = [1, 2, 3, 4, 5, 6];
shuffleInPlace(numbers);
console.log(numbers); // 元の配列がシャッフルされる

• メモリ効率的 (追加配列を使わない)
• 元の配列が書き換えられるため、不変性 (immutability) を重視しないコードで有用

✂ イミュータブル (元配列を残す)

function shuffle<T>(arr: T[]): T[] {
  const a = [...arr]; // 元の配列はそのまま
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

const numbers = [1, 2, 3, 4, 5, 6];
const shuffledNumbers = shuffle(numbers);
console.log(shuffledNumbers); // 新しい配列が返る
console.log(numbers); // 元の配列は変更されない

• 元の配列を変更せず、新しい配列を返す
• React / Redux / Vuex など「不変性を重視する環境」に適している

用途に応じて使い分けが可能です。

⏱ 計算量・メモリ使用量

項目	値 / 特性
計算量 (時間)	O(n) — 配列長 n に比例して線形時間
メモリ使用量	O(1)（ミュータブル版） または O(n)（コピーしてイミュータブル版）
シャッフルの性質	完全ランダム (uniform)、バイアスなし

この計算量・性質の良さにより、多くのライブラリ・言語標準で採用されてきた定番アルゴリズムです。

✔ よくある応用例

• カードゲーム (トランプをランダムに並べる)
• ガチャ / 抽選 / ランダムイベント
• ゲームにおけるランダムな配置 (マップ、モンスター、アイテムなど)
• A/B テストやランダムサンプリング (データ分析)
• UI / UX でのコンテンツ順序ランダム化 (例：スライドショー、クイズ問題)

実際、ほぼすべての言語標準ライブラリやゲームエンジンでは、内部で Fisher–Yates に準じたシャッフルを使っているケースが多いです。

⚠️ 注意点 — 「完全ランダム」を実現するために気をつけること

🎲 乱数生成器 (RNG / PRNG) の質

• Fisher–Yates 自体が完璧でも、使う乱数生成関数 (PRNG) の品質が低ければ偏りが出る可能性がある。特に、周期が短い、あるいは出力に偏りがある PRNG は危険。
• 例えば、単純な線形合同法 (LCG) や小さなビット幅の PRNG では、十分な乱数空間をカバーできず、52 枚のトランプなど要素数の多い配列では理論上すべての順列を生成できない可能性がある。

🔢 乱数の取り出し方 (範囲生成) による「モジュロバイアス」

• Math.random() * (i + 1) → Math.floor() の方法や、単純な % n (mod) を使って乱数を範囲に収める方法では、乱数分布の偏り (モジュロバイアス) が出る可能性がある。
• 特に、RNG の出力範囲と目的とする範囲の不整合 (例えば RNG が 0〜99 を返し、それを 0〜15 に落とすなど) の際は、あるインデックスが選ばれやすくなる。

→ 重要：もしセキュリティ／暗号／公平性／統計精度が求められる用途なら、乱数生成部分も慎重に選ぶべきです。

💡 よくある疑問・誤用のパターン

• オフバイワン

  • ループの上限やランダム範囲指定を間違えると、意図した「すべての順列を均等に出す」性質を失う。たとえば j = random(0, i-1) としてしまうと、ある並び (特に自身と入れ替えないケース) が除外され、バイアスが生じる。

• 擬似乱数の限界

  • 配列が大きい (たとえばトランプ全 52 枚など) 場合、PRNG の状態空間が順列数に対して足りず、多くの順列がそもそも生成不可能になる — 実質的に偏ったシャッフルに。

• 見た目ランダムでも不均等なソート式

  • sort(() => Math.random() - 0.5) のような「お手軽シャッフル」は、明示的に不均等な確率分布生成となり、実用には不向き。

🔍 まとめ

✅ 良い「使うべき」ポイント	❗ 注意すべきポイント
Fisher–Yates は O(n)、均等分布、シンプルで実装容易	乱数の質 (PRNG) や範囲生成でバイアスが入る可能性
インプレース／イミュータブル 両対応で用途に応じて使える	単純な sort + Math.random() は避けるべき

✅ 終わりに

Fisher–Yates シャッフルは、現代においても「事実上の標準」 — つまり 正しく公平なランダムシャッフル を実現したいなら、まずこれを覚えておくべきアルゴリズムです。

もしあなたがカードゲーム、ランダム並び替え、データサンプリング、ガチャ、ランダムイベントなどを実装するなら —「知らずにやってしまう」バイアスよりも、安全で公平、そして高性能な Fisher–Yates を使いましょう。