Fisher-Yates shuffle

Fisher-Yates shuffleは、配列をシャッフルするためのアルゴリズムです。Knuth shuffleとも呼ばれるようです。

以下の実装では、計算量はO(n)です。

参考: Fisher–Yates shuffle - Wikipedia

const N = 16;
const a = Array.from({ length: N }, (v, i) => i); // [0, 1, ..., 15]

for (let i = N - 1; i >= 1; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [a[j], a[i]] = [a[i], a[j]]; // Swap a[j] and a[i]
}

console.log(a);
// [7, 15, 1, 8, 11, 5, 13, 0, 2, 4, 6, 3, 12, 14, 9, 10]