【JavaScript】arr.sort(() => Math.random() – 0.5);がダメな理由の説明と適切なシャッフルの仕方

　AIにプログラムを任せる web サービスを試していて、次のコードが出力されて来ました。

// 入力
/* ランダムに配列を並び替える */
// 出力
arr.sort(() => Math.random() - 0.5);

　確かに入力した通りの内容のコードを出力してくれたのですが、大いに意図と異なるつくりのコードを返してきました。何故このコードがダメでランダムな並び替え、いわゆるシャッフルをするためにはどの様なコードが良いのかを説明します。

　まずダメであることの証明ですが、端的に言うと偏りが起きます。これは複数回コードを実行して結果を数えれば一目瞭然です。具体的には次です。

const result = {
  '1,2,3': 0,
  '3,2,1': 0,
  '2,1,3': 0,
  '2,3,1': 0,
  '1,3,2': 0,
  '3,1,2': 0,
};
for (let i = 0; i < 1e5; i++) {
  const arr = [1, 2, 3];
  // Math.random を使って並び替え
  arr.sort(() => Math.random() - 0.5);
  // ソート結果のカウントを増加
  if (!result[arr.toString()]) {
    result[arr.toString()] = 1;
  } else {
    result[arr.toString()]++;
  }
}
console.log(result);
/*
 {
  '1,2,3': 37387,
  '3,2,1': 31337,
  '2,1,3': 12394,
  '2,3,1': 6273,
  '1,3,2': 6234,
  '3,1,2': 6375
}
 */

　ものすごく結果が偏りました。このコードが無作為に一様な並び替えとしては使いものにならないことがわかります。なぜこうなるかには Arr.sort メソッドに渡す比較関数がどのタイミングでどう使われているかが重要です。これがわかるコードが次です。

const arr = [1, 2, 3];
arr.sort((a, b) => {
  const ret = Math.random() - 0.5;
  console.log({ a, b, ret: ret ? -1 : 1 });
  return ret;
});
console.log(arr);
// { a: 2, b: 1, ret: -1 }
// { a: 3, b: 2, ret: -1 }
// [ 1, 2, 3 ]

　1 や 3 が端に来やすいのがなんとなくイメージしやすいのではないでしょうか。例のコンソールの場合では、最初の一回目の比較で 1 が左端に来るのが確定し、次いで 2 と 3 を比較している感じです。3 と 1 の比較は 1 < 2 と 2 < 3 が成立するためにスキップされています。ソートアルゴリズムは高速化のために推移律（a ならば b かつ b ならば c が成り立つならば a ならば c となるという法則）が成立することを前提にしており、全ての大小関係を総当たりすることが稀なため、例の様な推移律が成立しない比較関数を渡すと偏りが生じます。

　正しく無作為に並び替えるアルゴリズムを手製するならばフィッシャーイェーツのシャッフルアルゴリズムをググって次の様なプログラムを使うといいです。これは全ての配置についてランダムな入れ替えを行うアルゴリズムであり、偏りなくソートが行われます。

const arr = [1, 2, 3];
const shuffleArray = (array) => {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
};
shuffleArray(arr);

　JavaScript 以外ならば shuffle 関数があるものが多いのでそちらを探すのも手です。

　余談ですが、件のAIは次の様に命令すれば適切に無作為な並び替えをするコードを返してくれました。

// 入力
/* 配列をシャッフルする */
// 出力
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function shuffle(array) {
var n = array.length, t, i;

while (n) {
i = Math.floor(Math.random() * n--);
t = array[n];
array[n] = array[i];
array[i] = t;
}

return array;
}

shuffle(array);