シャッフル

shuffle

要素の数と中味は決まっているが、ランダムな順序が欲しいような場合がある。

問題

シャッフルには明確な仕様や考え方がない。せいぜいごちゃ混ぜにするという意味のみ。

手動によるシャッフルでは、綺麗に混ざらない(最初に与えられた数列に対して有意な順列が含まれる)ことが知られている。

パーフェクトシャッフルだと元の順列に戻ってしまう。

単純実装では以下のようなものがある。

配列の2点をランダムに選び、その2点を交換する。それを適当な回数繰り返す。

これは品質が悪い上に遅い。

遺伝的アルゴリズムなどで時々使うのには適している。

始点から順に、それ自身と後方の配列上の1点をランダムに選び、交換する。次の配列位置に移動する。

これが恐らく最も妥当な方法。

配列は破壊するが、それ以外のリソースを一切使わない。

やや無駄があるが、細かなことを考えないなら、これが妥当。計算量は O(n) になる。

乱数生成関数を切り出しているのは、乱数生成方法の選択を容易にするため。

code:shuffle.js

function shuffle(a, generateRandomInt) {

for (var i = 0, last = a.length - 1; i < last; i++) {

var k = generateRandomInt(i, a.length);

if (i != k) {

}

}

return a;

}