配列のシャッフル

配列の要素をシャッフル(ランダムに並べ替える)shuffle(配列)関数を記述します。

shuffleを実行すると、要素の順序が異なる場合があります。例えば

          let arr = [1, 2, 3];

shuffle(arr);
// arr = [3, 2, 1]

shuffle(arr);
// arr = [2, 1, 3]

shuffle(arr);
// arr = [3, 1, 2]
// ...
        

すべての要素の順序は等しくなるはずです。例えば、[1,2,3]は[1,2,3]または[1,3,2]または[3,1,2]などとして並べ替えられ、各ケースが同等の確率で発生します。

簡単な解決策は次のようになります。

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

Math.random() - 0.5は正または負の乱数であるため、ある程度機能します。そのため、並べ替え関数は要素をランダムに並べ替えます。

しかし、並べ替え関数は本来このように使用されるものではないため、すべての順列が同じ確率になるわけではありません。

たとえば、以下のコードを考えてみます。これはshuffleを1000000回実行し、可能なすべての結果の出現をカウントします。

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

// counts of appearances for all possible permutations
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// show counts of all possible permutations
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

例の結果(JSエンジンに依存します)

          123: 250706
124425
249618
124880
125148
125223
        

バイアスが明らかです。123と213は他のものよりもはるかに多く表示されます。

コードの結果はJavaScriptエンジンによって異なる場合がありますが、このアプローチが信頼できないことはすでにわかります。

なぜ機能しないのか？一般的に言って、sortは「ブラックボックス」です。配列と比較関数をそこに投入し、配列がソートされることを期待します。しかし、比較の完全なランダム性によりブラックボックスは狂い、その狂い方はエンジンによって異なる具体的な実装に依存します。

タスクを実行する良い方法は他にもあります。例えば、フィッシャー-イェーツシャッフルと呼ばれる優れたアルゴリズムがあります。この考え方は配列を逆順にたどり、各要素をその前の要素とランダムに入れ替えることです

          function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // random index from 0 to i

    // swap elements array[i] and array[j]
    // we use "destructuring assignment" syntax to achieve that
    // you'll find more details about that syntax in later chapters
    // same can be written as:
    // let t = array[i]; array[i] = array[j]; array[j] = t
    [array[i], array[j]] = [array[j], array[i]];
  }
}
        

同じ方法でテストしてみましょう

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}

// counts of appearances for all possible permutations
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// show counts of all possible permutations
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

サンプル出力

          123: 166693
166647
166628
167517
166199
166316
        

これでよさそうです。すべてのパターンが同じ確率で表示されます。

また、パフォーマンスの観点から、フィッシャー-イェーツアルゴリズムははるかに優れており、「ソート」のオーバーヘッドはありません。