シャッフル実装
Fisher-Yatesアルゴリズムで実装されたgoodShuffleと巷で見つけたsort実装のbadShuffleを5個用意。
var goodShuffle = function (arr) {
var i, j, temp;
arr = arr.slice();
i = arr.length;
if (i === 0) {
return arr;
}
while (--i) {
j = Math.floor(Math.random() * (i + 1));
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
};
var badShuffle1 = function (arr) {
return arr.slice().sort(function () {
return Math.round(Math.random() * 2) - 1;
});
};
var badShuffle2 = function (arr) {
return arr.slice().sort(function () {
return Math.round(Math.random());
});
};
var badShuffle3 = function (arr) {
return arr.slice().sort(function () {
return Math.random() - Math.random();
});
};
var badShuffle4 = function (arr) {
return arr.slice().sort(function () {
return parseInt(Math.random() * 3, 10) - 1;
});
};
var badShuffle5 = function (arr) {
return arr.slice().sort(function () {
if (Math.random() > 0.5) {
return 1;
} else {
return -1;
}
});
};
均等に分布しているかを調べるメソッドを実装
同じ配列に対してシャッフルし、何番目に配置されたかを記録。1000回繰り返して平均を出すプログラムを実装。10個の要素をシャッフルするので、全ての要素でこの値が4.5に近ければ均等にシャッフルされたことになる。
var array = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'];
var times = 1000;
var trial = function (shuffle) {
var arr, average, elem, i, j, len;
average = {};
for (i = 0, len = array.length; i < len; i++) {
average[array[i]] = 0;
}
i = times;
while (i--) {
arr = shuffle(array);
for (j = 0, len = arr.length; j < len; j++) {
elem = arr[j];
average[elem] += j;
}
}
for (elem in average) {
average[elem] /= times;
}
return average;
};
結果
Fisher-Yatesアルゴリズム
4.5近辺なので均等に混ざっているといえる。
console.log(trial(goodShuffle));
{ A: 4.579,
B: 4.358,
C: 4.487,
D: 4.575,
E: 4.541,
F: 4.341,
G: 4.522,
H: 4.519,
I: 4.646,
J: 4.432 }
Array#sort実装
元のインデックスに沿って並ぶので全然混ざらない。
console.log(trial(badShuffle1));
{ A: 0.38,
B: 1.16,
C: 2.023,
D: 2.985,
E: 3.949,
F: 5.01,
G: 6.013,
H: 6.915,
I: 7.896,
J: 8.669 }
console.log(trial(badShuffle2));
{ A: 1.539,
B: 1.55,
C: 2.288,
D: 3.108,
E: 4.079,
F: 4.876,
G: 5.665,
H: 6.565,
I: 7.314,
J: 8.016 }
console.log(trial(badShuffle3));
{ A: 1.65,
B: 1.674,
C: 2.255,
D: 3.123,
E: 4.014,
F: 4.788,
G: 5.748,
H: 6.471,
I: 7.327,
J: 7.95 }
console.log(trial(badShuffle4));
{ A: 0.724,
B: 1.155,
C: 2.119,
D: 2.929,
E: 3.967,
F: 4.991,
G: 5.949,
H: 6.956,
I: 7.707,
J: 8.503 }
console.log(trial(badShuffle5));
{ A: 1.624,
B: 1.653,
C: 2.117,
D: 3.068,
E: 3.899,
F: 4.94,
G: 5.779,
H: 6.625,
I: 7.296,
J: 7.999 }
結論
Fisher-Yatesアルゴリズムを使おう。