Fisher-Yates shufflアルゴリズムを用いて自作で配列をシャッフルさせる

RubyやPython、Underscore.jsなどにはshuffle関数があり、簡単に配列の順番をランダムに入れ替えることはできますが、自作で配列やリストをランダムに入れ替える場合に、Fisher-Yates shuffleというアルゴリズムがあるので共有したいと思います

Fisher-Yates shuffle

Fisher-Yates shuffleは配列からランダムに要素を抽出し、入れ替えるアルゴリズムです。

  var length = array.length;
  for(var i = length - 1; i > 0; i--) {
      var j = Math.floor(Math.random() * (i + 1));
      var tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
  }

(Fisher-Yates shuffleアルゴリスムは英語版Wikipedia'Fisher-Yates shuffle'参照)

このアルゴリスムの特徴をまとめると以下のようになります

• 配列の全ての要素が最低１回ずつ入れ替えの対象となる
• 入れ替えられた要素が2回入れ替わることはない
• 配列の長さ分の計算量なので計算コストがかからなく高速
• 理論上偏りがない結果が得られる

最後に

シンプルかつ最適化されたアルゴリスムなので、要素をランダムに入れ替えるのアルゴリスムとしては最も有名だと思います。shuffle関数がない言語などで使ってみるといいですね

他の言語に用いられているshuffle関数については、こちらが参考になります
swiftでシャッフル関数
リストをシャッフルする
CoffeeScriptで配列のシャッフル

この記事も参考になります
Array#sort実装のshuffleは偏る