Fisher–Yates シャッフルは、配列を完全にランダムに並べ替える ためのアルゴリズムです。
このアルゴリズムの核心は、ランダムに選ぶ j の取りうる範囲がループごとに拡大(縮小)するという点にあります。
function shuffleArray(array) {
for (let i = 0; i < array.length; i++) { //配列を前から取得する版
// for (let i = array.length - 1; i > 0; i--) { //配列を後ろから取得する版
//以下は前も後ろもおなじ
const j = Math.floor(Math.random() * (i + 1)); //(i + 1)が増加(減少)するので J値の範囲も拡大(縮小)する
[array[i], array[j]] = [array[j], array[i]]; //[a,b] = [b,a]
}
return array;
}
j値の範囲 を拡大させていく実装(前から進む版)
-
for (let i = 0; i < array.length; i++) {j = Math.floor(Math.random() * i + 1)
j値の範囲 を縮小させていく実装
-
for (let i = array.length - 1; i > 0; i--) {-
j = Math.floor(Math.random() * (i + 1))- iが 5->4->3->2->1 と 1まで減少していく
-
どちらも数学的には同じ動きをしており、
両方の実装は Fisher–Yates シャッフルの正しいバリエーションであり、
どちらを使っても全ての順列が等確率で生成されます。
現在一般的なのは「j の範囲を縮小させる後ろから前へ進む実装」ですが、
これは古い環境での実装のしやすさや、誤実装を避けやすいという理由から
広く普及したものです。
// ❌ 間違ったシャッフル
for (let i = 0; i < array.length; i++) {
// (i + 1) iが増加していくことで jの範囲も拡大
const j = Math.floor(Math.random() * array.length); // ← 全範囲を選んでしまう
[array[i], array[j]] = [array[j], array[i]];
}
一方、現代の JavaScript ではどちらの書き方も問題なく使えるため、
アルゴリズムの流れを理解しやすい “j の範囲が前へ進むほど広がる実装”
を選ぶのも自然な選択です。
他にも以下の利点がある
- 配列の長さがわからなくても動く
- ストリーム（逐次読み込み）でもシャッフルできる
- メモリ効率が良い
🪑 席替えで理解する Fisher–Yates（j値の拡大版）
4人のメンバー [A, B, C, D] の席替えを行います。
席は 0〜3 の4つあり、最初は A〜D がそのまま 0〜3 の席に座っているものとします。
席替えルール
① 順番は前のA君から B → C → D の順
② くじ箱の中身はからっぽ
③ なので、各自、自分の席番号をくじにいれてからくじを引く
④ くじを引いたら番号を確認し、 引いた番号の席の人と自分の席を交換する
⑤ 引いたくじは箱にもどす
① 前から順番に、1人ずつ席を選ぶ
A → B → C → D の順番で席を決めます。
③ 各自、自分の席番号をくじにいれてからくじを引く
-
A（1人目） → 選べる席は 席0 のみ
→ くじは [0] だけ -
B（2人目） → 選べる席は 席0 か 席1
→ くじは [0,1] -
C（3人目） → 選べる席は 席0〜2
→ くじは [0,1,2] -
D（4人目） → 選べる席は 席0〜3
→ くじは [0,1,2,3]
④ 引いた席の人と自分の席と交換
🔍 例：席[1]のB が席[0]を引いた場合
- 席0には A が座っている
- B が席[0]に座る
-
A は B が元いた席 席[1] へ移動する
→ これが 交換 です
ゲームの開始
1人目：Aくんが席を決めます（i = 0）
Aくんは最初から 席 [0] に座っています。
-
選べる席：
0のみ -
くじ引き：
0 -
結果：そのまま席
[0]に座り続けます
現在の状態：[ A ]
2人目：Bくんが席を決めます（i = 1）
ここで Bくんの席 [1] が新しく追加されます。
-
選べる席：
0または1 -
くじ引き：
0, 1
もし 0 を引いた場合：
→ 席 [0] に座っている Aくんと席を交換（swap） します。
現在の状態（例）：[ B, A ]
3人目：Cくんが席を決めます（i = 2）
次に Cくんの席 [2] が追加されます。
-
選べる席：
0, 1, 2 -
くじ引き：
0, 1, 2
もし 1 を引いた場合：
→ 席 [1] に座っている Aくんと席を交換（swap） します。
現在の状態（例）：[ B, C, A ]
4人目：Dくんが席を決めます（i = 3）
最後に Dくんの席 [3] が追加されます。
-
選べる席：
0, 1, 2, 3 -
くじ引き：
0, 1, 2, 3
もし 3（自分の席） を引いた場合：
→ 誰とも交換せず、そのまま座ります。
最終状態（例）：[ B, C, A, D ]
🪑 席替えのルールで理解する（j値の範囲が縮小する版）
4人のメンバー [A, B, C, D] は、最初は席 [0,1,2,3] にそのまま座っています。
j 値が縮小する方法（後ろから前へ進む Fisher–Yates）では、
後ろの席から順番に、だれが座るかを 先生がくじ箱(A,B,C,Dの票が入っている)から票を引いて決めていきます。
席3 → 席2 → 席1 の順に、先生がくじを引き、
引かれた人をその席に座らせます。
ただし、生徒は最初から席に座っているため、
引かれた人と すでに席に座っている人と入れ替え（swap）が発生します。
最後の席0は、選ばれなかった人がそのまま座ります。
① 後ろの席から順番に誰がすわるか決める
席3 → 席2 → 席1 の順番で
「この席に誰が座るか」を先生がくじ引きで決めていきます。
よって席0には、残った人が座ることになります
② 一度引いたくじは箱にはもどさない
くじ箱は 1 つだけで、中には A, B, C, D の票 が 1 枚ずつ入っています。
先生がくじ箱から票を引いたら くじは箱に戻さず、残りの票を引いていくことになります
-
席[3] を決めるとき
→ 先生がくじ箱から 1 枚引く
→ くじ箱の中身は [A,B,C,D]（4票）
→引かれた人（例：C）は席3に座り、くじ箱から取り除かれる
→元々席[3]にはDがすわっていたので、Cがすわっていた席[2]にDが移動することで席の交換が生じます -
席[2] を決めるとき
→ くじ箱の中身は 残りの3票（例：A,B,D） -
席[1] を決めるとき
→ くじ箱の中身は 残りの2票 -
席[0] はそのまま
→ 席[０]にはいま座っている人がそのまま座ることになります
→ もしAが選ばれなかったらそのまま座り続けることになります。
③ 選ばれた人がその席に座る（すでに誰かが座っていた場合は交換）
その席に選ばれた人がその席にすわるため、もともとその席に座っていた人は、選ばれた人と席を交換することになります。
🎮 ゲーム開始
① 席[3] を決める（最初のくじ）
- くじ箱の中身：
[A, B, C, D] - 先生が 1 枚引く（例：C）
すると：
- 席3には D が座っている
- C を席3に座らせるため、C と D が席を交換する
状態例：[A, B, D, C]
② 席[2] を決める（次のくじ）
- くじ箱の中身：
[A, B, D]（C は取り除かれている） - 先生が 1 枚引く（例：A）
すると：
- 席2には D が座っている
- A を席2に座らせるため、A と D が席を交換する
状態例：[D, B, A, C]
③ 席[1] を決める（次のくじ）
- くじ箱の中身：
[B, D] - 先生が 1 枚引く（例：B）
すると：
- 席1には B が座っている
- すでに B が座っているので 交換は起きない
状態例：[D, B, A, C]
④ 席[0] はそのまま
- そのまま D が座る
- くじ箱の中身：
[D]
🏃♂️ 結論：後ろからでも前からでも結果は同じ！
- シャッフルの公平さ：完全に等確率（同じランダム度） 🎰
- 処理スピード（性能）：どちらも $O(N)$ で全く同じ ⚡