重み付きシャッフルの回答案

前回の続き。

問題：配列の中のある要素aに対してWaの重みが付いている。このとき、要素aが要素bより先に来る確率がWa/(Wa+Wb)となるようにシャッフルするにはどうすればよいか？

# 2007年08月28日 brazil brazil 1, TEMP, JAVASCRIPT, PROGRAMMING 最後の方法じゃだめなんだ...、ランダム

はてなブックマーク - 重み付けシャッフル、再び - snippets from shinichitomita’s journal

ランダムにそのまま重みを掛けた値でのソートだとだめなのは、絵を描いてみるとわかりそう。

PaとPbがそれぞれaおよびbの方が大きくなるエリアだけど、面積比はあきらかにWa:Wbじゃない。

まあその後色々考えて、多分これならそれっぽくシャッフルされるかな、というのを思いついたのだけど、どんなもんか。

var arr = [ [a,Wa], [b, Wb],  [c, Wc], ... ];

のような配列に対して、

function shuffle(arr) {
   return arr.map(function(a){ return [ a, Math.pow(Math.random() , 1.0/a[1]) ] })
             .sort(function(a, b){ return b[1] - a[1] })
             .map(function(a){ return a[0] });
}
shuffle(arr);

重み付けのところの関数は、0-1の区間の積分でWa/(Wa+Wb)になるように選んだ。

ちなみに重みが整数の場合は、前のエントリで書いたけど、Fisher-Yatesの応用でO(n)でできるはず。

function shuffle_intweight(arr) {
  var sarr = [];
  for (var i=0; i<arr.length; i++) {
    var wrap = [ arr[i], true ];
    for (var j=0; j<arr[i][1]; j++) sarr.push(wrap);
  }
  sarr = shuffle_fy(sarr); // Fisher-Yates Shuffle
  var ssarr = [];
  for (var i=0; i<sarr.length; i++) {
    if (sarr[i][1]) {
      sarr[i][1] = false;
      ssarr.push(sarr[i][0]);
    }
  }
  return ssarr;
}

答え合わせしたいのだけど、どっかに解答ってないのかな？