前回のエントリ、配列のランダマイズ、出来ますか？（前編）の続きです。
前回のエントリの最後では、次のようなコードを提示し、どこが問題なのかの疑問を提起しました。
// 配列の初期化
var a = [];
for(var i = 0; i < 1000; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その2
for(var i = 0; i < a.length; i++) {
swap(i, (Math.random() * a.length) | 0);
}
ランダマイズのコードの厄介なところは、1回2回実行したところで問題がわからない点で、このプログラムもぱっと見た感じではきちんとランダマイズされているように見えます。ではどうやって問題があるかを判断するかといえば、ランダマイズで問題があるというのは、最終結果がランダムになっていないことでしょう。というわけで、プログラムをちょっと改造して、実際に出力結果の偏りを確認してみましょう。
var output = {};
for(var c = 0; c < 1000000; c++) {
// 配列の初期化
var a = [];
for(var i = 0; i < 3; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その2
for(var i = 0; i < a.length; i++) {
swap(i, (Math.random() * a.length) | 0);
}
var result = a.join();
output[result] = (output[result] | 0) + 1;
}
for(var key in output) {
console.log(("00000" + output[key]).substr(-6) + " " + key);
}
100万回実行して、ランダマイズした結果を集計するプログラムです。わかりやすいように、配列の要素を3つにしました。[0,1,2]の配列をランダマイズすると、結果は[0,1,2][0,2,1][1,0,2][1,2,0][2,0,1][2,1,0]の6つのどれかになるはずですね。正しいランダマイズならば、それぞれの確率が1/6になるはずです。
ところが…自分の環境で実行すると、出力結果は次のようになりました。
147337 2,1,0
148202 0,1,2
148543 2,0,1
185066 0,2,1
185119 1,0,2
185733 1,2,0
この通り、見事に偏っています。なぜでしょうか？
これを理解するために、実際のアルゴリズムの中で何が起こっているのか追ってみましょう。プログラムを次のように改造します。
// 配列の初期化
var a = [];
for(var i = 0; i < 3; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その2
for(var i = 0; i < a.length; i++) {
var r = (Math.random() * a.length) | 0;
swap(i, r);
console.log(r + " : " + a.join());
}
1回1回のシャッフルで、何番と何番を入れ替えたかを表示するようにしています。その実行例がこちらです。
1 : 1,0,2
1 : 1,0,2
0 : 2,0,1
まず、配列0番目と1番目を入れ替えて[0,1,2]→[1,0,2]、次に配列1番目と1番目を入れ替えて（要するに何も入れ替えない）[1,0,2]→[1,0,2]、最後に配列2番目と0番目を入れ替えて[1,0,2]→[2,0,1]、最終的に[2,0,1]が得られました。
このシャッフル方法だと、それぞれの桁で3通りのシャッフルが可能であるのはお分かりになると思います。とすると、全体のシャッフル方法は、3×3×3=27通りのシャッフル方法が存在します。一方、シャッフル結果は前に書きましたとおり[0,1,2][0,2,1][1,0,2][1,2,0][2,0,1][2,1,0]の6つの結果のどれかになるはずです。もうこの時点で、このアルゴリズムだと偏りが出ることが確定的に明らかになっております。
具体的に、3桁の場合の全通りの可能性を調べるプログラムを書いてみましょう。
// 配列の初期化
var a = [];
for(var i = 0; i < 3; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
var output = {};
function recursive(digit) {
if(digit == a.length) {
var key = a.join();
output[key] = (output[key] || 0) + 1;
return;
}
for(var i = 0; i < a.length; i++) {
swap(digit, i);
recursive(digit + 1);
swap(digit, i);
}
}
recursive(0);
for(var key in output) {
var r = ("000000" + output[key]).substr(-4);
console.log(r + ":" + key);
}
再帰を使って全通りのシャッフルの組み合わせを確かめ、そのシャッフルの場合に最終的な結果になるかを集計するプログラムです。これを実行すると次のようになります。
0004:2,0,1
0005:1,2,0
0005:1,0,2
0004:2,1,0
0005:0,2,1
0004:0,1,2
27通りのうち、4/27と5/27の差が出来ているのがおわかりになると思います。この偏りの差が、最初にお見せした100万回のシャッフルの結果に一致するわけです。
なお、3桁なのでこの程度の差になっていますが、桁数が大きくなると偏りはどんどんとひどくなっていきます。たとえば4桁の場合は
0008:3,0,1,2
0008:3,1,2,0
0009:0,3,2,1
0009:2,1,0,3
0009:3,0,2,1
0009:3,1,0,2
0010:0,1,2,3
0010:0,1,3,2
0010:0,2,1,3
0010:1,0,2,3
0010:2,3,1,0
0010:3,2,0,1
0010:3,2,1,0
0011:0,3,1,2
0011:1,3,0,2
0011:1,3,2,0
0011:2,0,1,3
0011:2,0,3,1
0011:2,1,3,0
0011:2,3,0,1
0014:0,2,3,1
0014:1,2,0,3
0014:1,2,3,0
0015:1,0,3,2
回数でソートすると上記のような結果になり、一番出にくい組み合わせと一番出やすい組み合わせで倍近くの差があります。8桁にすると、
0128:7,0,1,2,3,4,5,6
0134:6,7,1,2,3,4,5,0
0152:7,0,1,3,4,2,5,6
0153:5,7,1,2,3,4,0,6
（…中略…）
1705:1,2,3,4,5,0,7,6
1875:1,2,0,4,5,6,7,3
1875:1,2,3,4,0,6,7,5
1931:1,2,3,0,5,6,7,4
と、なんと一番出やすいパターンと出にくいパターンで、結果の組み合わせに10倍以上も差がついてしまうのです。この結果をしっていれば、このアルゴリズムは到底実運用にて使用出来ないことがおわかりになるかと思います。
最後に、正しいアルゴリズムを紹介しましょう。以上からわかるとおり、すべての出方の組み合わせが1通りになるように実装すれば問題がないわけです。すなわち、
// 配列の初期化
var a = [];
for(var i = 0; i < 3; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
var output = {};
function recursive(digit) {
if(digit == a.length) {
var key = a.join();
output[key] = (output[key] || 0) + 1;
return;
}
for(var i = digit; i < a.length; i++) {
swap(digit, i);
recursive(digit + 1);
swap(digit, i);
}
}
recursive(0);
for(var key in output) {
var r = ("000000" + output[key]).substr(-4);
console.log(r + ":" + key);
}
再帰部分(20行目)をこのように変えれば、すべてのパターンを1度ずつ網羅するようになります。実行結果はこちらです。
0001:0,1,2
0001:0,2,1
0001:1,0,2
0001:1,2,0
0001:2,1,0
0001:2,0,1
それをシャッフルのアルゴリズムにすれば、次のようになります。
// 配列の初期化
var a = [];
for(var i = 0; i < 1000; i++) {
a[i] = i;
}
function swap(s, d) {
var t = a[s];
a[s] = a[d];
a[d] = t;
}
// ランダマイズ、その3
for(var i = 0; i < a.length; i++) {
swap(i, ((Math.random() * (a.length - i)) + i) | 0);
}
念のために実際の出力を確認してみても、安心の結果です。
167256 2,0,1
166295 2,1,0
166589 1,2,0
166698 0,2,1
166870 0,1,2
166292 1,0,2
なお、上のコードを言葉で説明すると、「とりあえず配列からランダムで1個取って、次はそれを取り除いた中からさらにランダムで1個とって…」という処理になります。コード的には次のコードと同じです。
// 配列の初期化
var a = [];
for(var i = 0; i < 1000; i++) {
a[i] = i;
}
var output = [];
while(a.length) {
var r = (Math.random() * a.length) | 0;
output.push(a[r]);
a.splice(r, 1);
}
元の配列からランダムで結果配列に一つずつ追加し、選択した要素を元の配列から削除するプログラムです。こうやって見てみると、問題なくランダマイズしているコードであることがわかりやすいのではないでしょうか？
配列のランダマイズをするときは、最終結果の組み合わせが偏らないように気をつけましょう。