[Javascript] 配列をシャッフル(ランダムソート)する方法

フィッシャー – イェーツのシャッフル

[C#] 配列をランダムソート(シャッフル)する方法

以前、C#でコレクションをシャッフルする方法を調べましたが、今回は Javascript で配列をシャッフルする方法を調べます。シャッフルには、フィッシャー – イェーツのシャッフル なるランダムな順列を生成するアルゴリズムを使います。

このアルゴリズムがどのようなものかは、例によって、Wikipedia に詳しくあります。その特徴部分を引用します。

• 極めて効率的であり、時間的空間的な計算量は最適である。
• 偏りのない良質な乱数をもとにするならば、生成結果も偏りがないことが保証される。
• 他のアルゴリズムと比較してもその長所は変わらない。
• もしも結果の順列の一部のみが必要であれば、必要な数の順列が生成された時点で処理を中断すればよい。

Javascript サンプル

まずは実装例を以下に示します。

var array = [1,2,3,4,5,6,7,8,9,10];
for(i = array.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}
console.log(array);

アルゴリズム

配列の後ろから順にループする

for(i = array.length - 1; i > 0; i--) {}

配列の後ろの要素から順にループして、取り出した要素をシャッフル（入れ替え）します。こうすることですべての要素がすくなくとも1回はシャッフルされるようになります。

入れ替え対象の要素をランダムに取得する

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

i番目より小さい数(0 ～ i-1)をランダムで選びます。

要素の入れ替えを行う

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

i番目の要素とランダム(0 ～ i-1)で選んだ要素を入れ替えます。ここで入れ替わったi番目の要素はシャッフル済の要素となって、再度入れ替えられることはありません。

上記処理を繰り返す

残りの要素が1つになれば、入れ替えできないので処理終了、シャッフル完了です。

まとめ

実装もシンプルで効率的なシャッフルアルゴリズムでした。Javascriptでの例でしたがもちろん他の言語でも実装可能です。