JSでFisher-Yatesアルゴリズムを使って配列をシャッフルする

今回はJavaScriptを使って説明しますが、どの言語でも変わりません。短いコードで効率のよいプログラムです。ほかのシャッフルアルゴリズムと比べて計算量がO(n)であり、偏りがないことがこのアルゴリズムの特徴です。

Fisher-Yates

デモを用意しました。

ソースコード

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

for(var i = arr.length - 1; i > 0; i--){
  var j = Math.floor(Math.random() * (i + 1));
  var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

console.log(arr);

配列の後ろから

for(var i = arr.length - 1; i > 0; i--){

配列の一番後ろの要素から順にシャッフルしていきます。

ランダム値を生成

var j = Math.floor(Math.random() * (i + 1));

配列のi番目より前の範囲でランダム値を出します。

交換

var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;

あとはそれらを交換すればシャッフルできます。