2006-08-28

JavaScriptで配列をシャッフル

配列をシャッフル、つまりランダムに要素の位置を入れ替えるというのを、sortメソッドを使ってやってみたのだけど、明らかにダメダメなものになってしまった。その後、あーでもないこーでもないと考えたのだけど、算数が得意すぎて頭が痛くなった。ということを某所でぼやいたらはてのくんがコードを見つけてくれた。どうやらFisher-Yatesという有名なアルゴリズムでやると良いらしい。

最初に書いたコードは、

var a = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
a.sort(
  function (a, b) {
    return Math.ceil(Math.random() * 3) - 2;
  }
);

というもの。sortメソッドは、パラメータに与えられた関数が負の値・0・正の値を返すことによって要素の順序を決定するので、その関数がランダムに値を返せばランダムにソートされるであろうというコード。結果は偏るというか、アルゴリズムがおかしいと予想される結果になった。何気にInternet Explorer 6ではシャッフルされているっぽい感じになるのだけど。

その後、ランダムにsortした後reverseしてまたランダムにsortとかもやってみたりと、いろいろ考えたけど、結局頭がこんがらがるだけでちゃんとシャッフルされているという確信が得られない。

はてのくんがCode Snippetsから見つけてくれたArray Shuffle //JavaScript Functionでは、Fisher-Yatesなるアルゴリズムを利用しているらしい。このコードは理解しづらかった(シャッフルされることは確認したけど)ので、Fisher-Yatesについて調べてみると、どうやらPerlクックブック〈VOLUME1〉にも載っている有名なアルゴリズムだそうで。記憶に無いです。

Perlクックブックのレシピ4.18 配列の要素をランダムに並べ替えるでは、

sub fisher_yates_shuffle {
  my $array = shift;
  my $i;
  for ($i = @$array; --$i; ) {
    my $j = int rand ($i+1);
    next if $i == $j;
    @$array[$i,$j] = @$array[$j,$i];
  }
}

という風になっている。拙い理解でJavaScriptに移植すると、

function shuffle(list) {
  var i = list.length;

  while (--i) {
    var j = Math.floor(Math.random() * (i + 1));
    if (i == j) continue;
    var k = list[i];
    list[i] = list[j];
    list[j] = k;
  }

  return list;
}

となる(と思う)。サンプル・ページを作成して試したところ、ちゃんとシャッフルされているようだ。並べ替えるというよりも、入れ替えるという形。

最終的にはどうやら解決した(と思う)ので、勉強にもなったし良かったのだけど、こういうアルゴリズム的なお話はやっぱり知っているといないでは雲泥。アルゴリズム系の勉強のためにもPerlクックブックをちゃんと読み直そう。重いんだよな、アレ。