配列のシャッフル
解説/アルゴリズム
[1, 2, 3, 4, 5]
配列を用意する。
[1, 2, 4, 5, {3}](3 が選ばれたので最後尾に移動)
配列の中からランダムに値を取り出して最後尾に格納する。
[2, 4, 5, {1, 3}](1 が選ばれたので最後尾に移動)
格納した値以外でまた上記手順を繰り返す。
[2, 5, {4, 1, 3}](4 が選ばれたので最後尾に移動)[5, {2, 4, 1, 3}](2 が選ばれたので最後尾に移動)[5, 2, 4, 1, 3]
最後の一つをランダムに選ぶ必要は無いので、これでシャッフルが完了になる。
コード例
function shuffle<T>(a: T[]): T[] {
// 後ろから配列を走査していく
for (let i = a.length - 1; i > 0; i--) {
// 0～iのインデックスをランダムに選択
const j = Math.floor(Math.random() * (i + 1));
// iとjの位置にある要素を交換
[a[i], a[j]] = [a[j], a[i]];
}
return a;
}
後ろから配列を走査していき、i 番目の要素を 0 ～ i 番目の要素のどれかに置き換える。
自身の要素も含まれるので、結果的に置き換えが発生しない可能性もある。
このアルゴリズムは、前から走査をしてもいいのだが、ランダムなインデックスを作るコードが若干複雑になる。（i ～ length - 1）
const num = 10000;
const len = 10;
const avg = ((len - 1) / 2) * num;
const numbers: number[] = [];
const totals: number[] = [];
for (let i = 0; i < len; i++) {
numbers[i] = i;
totals[i] = 0;
}
for (let i = 0; i < num; i++) {
shuffle(numbers);
for (let j = 0; j < len; j++) {
totals[j] += numbers[j];
}
}
const result = totals.map((v, i) => {
return `${i}: ${v} (${((v / avg) * 100).toFixed(2)}%)`;
});
console.log(result);
0: 45361 (100.80%)
1: 44801 (99.56%)
2: 44644 (99.21%)
3: 44701 (99.34%)
4: 45440 (100.98%)
5: 44797 (99.55%)
6: 44999 (100.00%)
7: 45096 (100.21%)
8: 44708 (99.35%)
9: 45453 (101.01%)
シャッフルを 10000 回実行した、要素ごとの合計値と、平均値との比率。