重み付けシャッフル、再び - snippets from shinichitomita’s journal

昔のエントリ。一年前。

置換によるシャッフルと違って、weight値のところを適当に変化させれば、要素ごとに重みづけてのシャッフルもできると思う。たとえばよく聞く曲は優先的に前の方に持ってくるとか、その逆とか。iTunesのシャッフルがそうなってるかどうかは知らないけれども。
JavaScriptの配列をsort関数でシャッフルする - snippets from shinichitomita’s journal

今頃、そういうことをやろうとして、適当じゃなくちゃんと実装しようとして、はまってきた。まあ適当にやればそれでもありなだけに、逆に気にかかるという罠。
つまり、重み付けシャッフル、というのがあったとして、さて一体どういうのが正しい問題設定なのかが、よくわからない。ある要素がWの重みを持っていたとして、どのような振る舞いのシャッフルを期待するのが妥当なのか。

まずは整数倍の場合で考えてみる。そのときは、何となくだがその要素を重みの分要素をコピーして増やしてみることにするのがよさそうだ。
たとえば、配列[a,b,c,d]があり、それぞれ a:2, b:1, c:1, d:3 の重み付けのとき

[a, a, b, c, d, d, d]

のような配列にしてからFisher-Yatesでシャッフルを行う。その後、結果を先頭からスキャンしていって、すでにスキャンされた文字を抜いて、配列に重複がないような状態にする。
これが、おそらく整数倍に重み付けされたシャッフルの結果として求められるものなのだろうか。確信はないけど、それっぽくはある。

じゃあ、重みが非整数の場合ってのはどうなのか。整数の延長で考えるのが正しいのだとすると、きっと問題はこうなるのかな。
「配列の中の要素a とbの重みがそれぞれWa, Wbのとき、aがbよりも配列の先に来る確率がWa/(Wa+Wb)であるように並べ替えること」
当たりかな？じゃあ解答はどうすればいい？

ちなみにこれではないことはよくわかった。

Array.prototype.shuffle = function() {
   return this.map(function(a){ return { weight: Math.random() * a[1], value: a[0] } })
              .sort(function(a, b){ return b.weight - a.weight })
              .map(function(a){ return a.value });
}
[ ['a', 2], ['b', 1], ['c', 1], ['d', 3] ].shuffle()

残念。一応重い方が前の方に出て来るけど、重みに指定した値の比率よりももっと偏ってしまう。