「シャッフル」ボタンを押したとき、結果は本当にランダムですか？多くの人は「乱数関数を呼ぶだけで公平なランダム順列が得られる」と思っていますが、実際には間違った実装によって特定の順列が他より多く出現する「隠れた偏り」が生じます。本記事では、正しいシャッフルアルゴリズムであるFisher-Yates Shuffleの仕組みを解説します。
1. 「公平なランダム順列」とは何か
3つの要素 [A, B, C] があるとすると、可能な順列は 3! = 6 通りです：
ABC ACB BAC BCA CAB CBA「公平なシャッフル」とは、これら6通りの順列がそれぞれ 1/6 ≈ 16.67% の確率で出現することを意味します。ある実装で ABC が20%の確率で出現し他が16%しか出ない場合、それは「ランダムに見える」だけで統計的には偏ったシャッフルです。
2. よくある落とし穴：sort() + Math.random()
多くの開発者が書いたことのあるコード（JavaScript）：
// よく見るが偏りのある実装
array.sort(() => Math.random() - 0.5);一見合理的に見えますが、実際には深刻な偏りがあります：
- ソートアルゴリズムは一貫した比較を前提とする：クイックソートやマージソートは同じ2要素を複数回比較することがあります。ランダムな比較関数は毎回結果が変わるため、アルゴリズムが予期しないパスをたどります。
- 数学的に均一分布を保証できない：比較ソートの計算量はO(n log n)で、n log n回の比較しか行いません。n個の要素にはn!通りの順列があり、n!がO(n log n)で区別できる状態数をはるかに超えると、一部の順列が「まとめられて」高い確率で出現します。
[1,2,3] に対してsort+randomを100万回実行すると、一部の順列が16.67%ではなく約20%出現することがわかります。偏りは小さいですが、公平性が求められる抽選では許容できません。
3. Fisher-Yatesアルゴリズムの仕組み
Fisher-Yates Shuffle（現代版はKnuth Shuffleとも呼ばれる）は1938年にRonald FisherとFrank Yatesが考案し、Donald Knuthが『The Art of Computer Programming』で現代的な形に発展させました。
アルゴリズムの手順（n要素の配列）：
- 最後の要素（インデックス n-1）から始め、インデックス1まで逆方向に反復します。
- 現在のインデックス
iに対して、[0, i]（両端含む）から乱数でインデックスjを選びます。 array[i]とarray[j]を交換します。i-1で同じ処理を繰り返し、i = 1まで続けます。
// Fisher-Yates Shuffle（JavaScript 正しい実装）
function shuffle(array) {
const a = [...array]; // 元の配列を変更しない
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;
}4. なぜFisher-Yatesは均一分布を保証するのか
[A, B, C] を例に確率を分析します：
| ステップ | 操作 | 確率 |
|---|---|---|
| i=2 | [0,1,2]からjを選ぶ（3番目の位置の要素を決定） | 各1/3 |
| i=1 | [0,1]からjを選ぶ（2番目の位置の要素を決定） | 各1/2 |
| i=0 | 1番目の位置には残りの要素が固定される | 1 |
任意の順列が出現する確率：
P(特定の順列) = 1/3 × 1/2 × 1 = 1/6数学的に完全に均一です。n個の要素に対して、各順列の出現確率は正確に 1/n! となります（乱数関数自体が均一分布であることが前提）。
5. グループ分けへの応用
「ランダムグループ分け」は「シャッフル ＋ 均等配分」の2ステップです：
function randomGroup(names, groupCount) {
const shuffled = shuffle(names); // ステップ1：Fisher-Yatesシャッフル
const groups = Array.from({ length: groupCount }, () => []);
shuffled.forEach((name, i) => {
groups[i % groupCount].push(name); // ステップ2：順番に各グループへ
});
return groups;
}ラウンドロビン配分（i % groupCount）により、各グループの人数差は最大1人です。10人を3グループに分けると4・3・3人になり、4・4・2のような不均等な分配は起きません。
6. よくある誤りのまとめ
| 誤り | 問題 | 正しい方法 |
|---|---|---|
| array.sort(() => Math.random() - 0.5) | 統計的偏り | Fisher-Yatesを使う |
| 各要素に乱数キーを割り当てて並べ替え | 理論上正しいがO(n log n) | Fisher-YatesはO(n) |
| 先頭k個だけをランダムに選ぶ | 完全なシャッフルではない | Fisher-Yatesの最初のk回＝非復元抽出 |
| 同じ位置を複数回ランダムに交換 | 交換確率が不均一 | 各位置は1回だけ交換する |
7. まとめ
シャッフルは単純に見えますが、「見た目がランダム」と「統計的に均一」は別物です。Fisher-YatesアルゴリズムはO(n)の計算量と数学的な均一性の保証を兼ね備えた、公平性が求められるあらゆる場面での標準的な選択肢です。
実際のランダムグループ分けを試したい方は、本サイトのリストグループ化ツールをご利用ください。名前を入力するだけで、公平なシャッフルやグループ分けが即座に行えます。