JavaScriptで配列を正しくシャッフル

October 14, 2018

JavaScript の Array をシャッフルする方法について調べてみたら，ちょっとだけおもしろかったのでブログに書くことにしました．

Fisher–Yates アルゴリズム

まず最初に，偏りの少ない公平なシャッフルする正しい方法を説明します．Fisher–Yates shuffle というアルゴリズムです．（こちらに素晴らしい解説があります．）

トランプの束があり，これをシャッフルしたいとしましょう．束の中からランダムに 1 枚ずつ選び，束の隣に新しい束（シャッフル済の束）として重ねていきます．これが Fisher–Yates シャッフルです．

30secondsofcode.orgでは以下のような実装を紹介しています．

const shuffle = ([...arr]) => {
  let m = arr.length;
  while (m) {
    const i = Math.floor(Math.random() * m--);
    [arr[m], arr[i]] = [arr[i], arr[m]];
  }
  return arr;
};

https://github.com/30-seconds/30-seconds-of-code#shuffle

ざっくりした手順は以下の通りです．

長さが $N$ の配列がある．
$[0, m-1]$ の区間からランダムな要素番号を取得し，$m$ 番目の要素と入れ替える．
$m$ は $N$ からスタートし，1 つずつ減らしていき，0 になるまで繰り返す．

$m$ は未シャッフルな要素の数であると考えるとわかりやすいです．ここでの 1 つのポイントは，$[0, m-1]$ の区間に含まれる要素の数と $m$ との和が常に $N$ であるという点です．

上述したトランプの束の例では，「未シャッフルの束」の「シャッフル済の束」の 2 つが登場しました．もしもそれぞれを別の配列として扱うとしたらどうなるでしょう．以下のコードは，トランプの例を愚直にシミュレートした非効率な実装です．

// 非効率なバージョン
const insufficientShuffle = ([...arr]) => {
  const copy = [];
  let m = arr.length;
  while (m) {
    const i = Math.floor(Math.random() * m--);
    copy.push(arr.splice(i, 1)[0]);
  }
  return copy;
};

上のコードは正しく動作しますが，splice() がイテレーションごとに要素をシフトするため効率が悪いです．先ほどの実装は「$[0, m-1]$ の区間に含まれる要素の数と $m$ との和が常に $N$ である」という事実により，1 つの配列の要素をスワップするだけのシンプルな実装になっていて計算効率も良いです．

偏りが出てしまう不公平なシャッフル

Fisher–Yates shuffle が良いアルゴリズムであることは分かりましたが，偏りが生じてしまう実装は何が悪いのでしょうか．

実は，「JavaScript 配列シャッフル」でググって最初に見つけたコード（良くない実装）は以下です．

array.sort(() => Math.random() - 0.5);

このシャッフルの問題点はこちらの記事が指摘しています．実験してみるとかなり大きな偏りが確認できます．

混ぜすぎ注意...？

Fisher–Yates shuffle では要素を入れ替えるランダムの位置を $[0, m-1]$ から選んでいました．これを$[0, N-1]$から選ぶようにするとどうなるでしょうか．つまり，ランダムに入れ替える範囲を常に配列の全ての要素にします．実装は以下の通りです（Naïve shuffle と呼ぶそうです）．

const naiveShuffle = ([...arr]) => {
  for (let m = arr.length; m > 0; m--) {
    const i = Math.floor(Math.random() * arr.length);
    [arr[m], arr[i]] = [arr[i], arr[m]];
  }
};

実は，この実装方法ではシャッフルの結果に無視できないほどの偏りが生じます．なぜ偏ってしまうのかについて興味がある方は~~疲れたので~~こちらの記事をご覧下さい．

JavaScriptで配列を正しくシャッフル

Fisher–Yates アルゴリズム

偏りが出てしまう不公平なシャッフル

混ぜすぎ注意...？

参考