配列のシャッフル

配列の要素をシャッフル(ランダムに再配置)する関数 shuffle(array) を書いてください。

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);
}

// 可能性のあるすべての順列の出現数
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('')]++;
}

// 結果を表示します
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

結果例は次の通りです(V8, 2017/7):

          123: 250706
124425
249618
124880
125148
125223
        

明らかにバイアスがあることが分かります: 123 と 213 は他のものよりはるかに多く出現しています。

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

なぜ上手く動作しないのでしょうか？一般に、sort は “ブラックボックス” です: 配列と比較関数をそこに投げ、配列がソートされることを期待します。しかし、比較の完全なランダム性によりブラックボックスが狂ってしまい、どの程度狂ってしまうかはエンジンによって異なる具体的な実装に依存します。

このタスクをするための他の良い方法があります。例えば、Fisher-Yates shuffle と呼ばれる素晴らしいアルゴリズムがあります。この考えは、逆順に配列を見ていき、各要素をその前のランダムな要素と入れ替えます。

          function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // 0 から i のランダムなインデックス
    [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
        

良い感じに見えます: すべての順列は同じ確率で表示されています。

また、Fisher-Yates アルゴリズムはパフォーマンスの面で遥かに優れており、“ソート” のオーバヘッドがありません。