JavaScript で配列をランダム化またはシャッフルする
- JavaScript エンジンによる配列のシャッフル
- 単純なアルゴリズムのランダム性を測定する
-
Fisher-Yatesのシャッフルアルゴリズムを用いた配列のシャッフル -
Underscore.jsやLo-Dashライブラリを使って配列をシャッフルする
JavaScript で配列をシャッフルするには、シャッフルアルゴリズムを実装したり、ライブラリにある既存のシャッフル関数を使用したりと、様々な方法があります。
配列をシャッフルするということは、配列の要素をランダムに並べるということなので、配列をどのようにしてランダム性を持たせて並べ替えたり、並べ替えたりするかに主に依存します。
配列をランダムに並べ替えたり、シャッフルしたりする方法を見ていきましょう。
JavaScript エンジンによる配列のシャッフル
まずは単純な配列シャッフリングアルゴリズムを実装してみましょう。配列を array.sort() でソートしますが、Math.random() - 0.5 と -0.5 の式で生成されたランダム性を利用することで、アルゴリズムを呼び出すたびにランダムな値が正か負のどちらかになるようにします。
この単純なアルゴリズムを JavaScript エンジンの力を借りて実装し、Console.log() を使ってシャッフルされた配列をコンソールに出力してみよう。
function shuffleArray(inputArray) {
inputArray.sort(() => Math.random() - 0.5);
}
var demoArray = [1, 3, 5];
shuffleArray(demoArray);
console.log(demoArray);
出力：
[1, 5, 3]
単純なアルゴリズムのランダム性を測定する
その配列の順列の確率を計算して、実装したアルゴリズムがどれほど優れていてランダムであるかを確認できます。
そのランダム性の測定方法を見てみましょう。
- すべての順列の出現をカウントする辞書を作成します。
- 1000000 回実行され、毎回形成された順列のカウントを増加させるループを作成します。
- すべての可能な順列のカウントを出力し、それらの間の確率を観察します。
この単純な測定アルゴリズムは以下のように実装できます。
function shuffleArray(inputArray) {
inputArray.sort(() => Math.random() - 0.5);
}
// counts of the appearances for all possible permutations
var countDic = {
'153': 0,
'135': 0,
'315': 0,
'351': 0,
'531': 0,
'513': 0,
};
// Creating the loop
for (var i = 0; i < 1000000; i++) {
var arr = [1, 5, 3];
shuffleArray(arr);
countDic[arr.join('')]++;
}
// Print the counts of all possible permutations
for (var key in countDic) {
console.log(`${key}: ${countDic[key]}`);
}
出力：
135: 62256
153: 375832
315: 62976
351: 311865
513: 124518
531: 62553
上の出力を見ると、135、315、531 が他のものに比べて非常に少なく、似たようなカウントになっていることがわかります。
Fisher-Yates のシャッフルアルゴリズムを用いた配列のシャッフル
JavaScript エンジンに基づいたこの単純なアルゴリズムは、過去のセクションでは信頼性に欠けるものでしたが、効率と信頼性に関しては Fisher-Yates と呼ばれる優れたアルゴリズムの方が優れています。
Fisher-Yates アルゴリズムの背後にある考え方は、配列を逆順に歩き、各要素をその前のランダムな要素と入れ替えるというものです。Fisher-Yates はシンプルですが、非常に効率的で高速なアルゴリズムです。
それでは、Fisher-Yates アルゴリズムを実装してみましょう。
function fisherYatesShuffle(arr) {
for (var i = arr.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1)); // random index
[arr[i], arr[j]] = [arr[j], arr[i]]; // swap
}
}
var tmpArray = [1, 3, 5];
fisherYatesShuffle(tmpArray);
console.log(tmpArray);
それでは順を追って説明していきましょう。
for(var i =array.length-1 ; i>0 ;i--)配列の上を逆順に歩くforループ。Math.floor( Math.random() * (i + 1) )0 から i までの範囲のランダムインデックスを生成します。[arr[i],arr[j]]=[arr[j],arr[i]]は、Destructuring Assignment構文を用いてarr[i]とarr[j]の要素を入れ替えています。
出力：
(3) [3, 1, 5]
先ほどと同じように Fisher-Yates をテストしてみよう。
// counts of the appearances for all possible permutations
var countDic = {
'153': 0,
'135': 0,
'315': 0,
'351': 0,
'531': 0,
'513': 0,
};
// Creating the loop
for (var i = 0; i < 1000000; i++) {
var arr = [1, 5, 3];
fisherYatesShuffle(arr);
countDic[arr.join('')]++;
}
// Print the counts of all possible permutations
for (var key in countDic) {
console.log(`${key}: ${countDic[key]}`);
}
出力：
135: 166734
153: 166578
315: 166908
351: 166832
513: 166535
531: 166413
上の出力から、Fisher-Yates アルゴリズムと先ほど実装した単純なアルゴリズムとの間に大きな違いがあり、Fisher-Yates アルゴリズムがどれだけ信頼性の高いものであるかがわかります。
Underscore.js や Lo-Dash ライブラリを使って配列をシャッフルする
有名な Underscore.js ライブラリには、アルゴリズムの実装を書かなくても配列を直接ランダム化できるシャッフル関数もあります。
以下に _.shuffle() メソッドを使った例を見てみましょう。
まず、HTML テンプレートの中に Cloudflare CDN を使ってライブラリをインポートする必要があります。
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>
そして、_.shuffle() メソッドを使って以下のようにします。
var tmpUnderscoreArray = [1, 3, 5];
resultArray = _.shuffle(tmpUnderscoreArray);
console.log(resultArray);
出力：
(3) [1, 5, 3]