きまぐれ日記: Schwartzian Transform でランダムシャッフル

Schwartzian Transform を使って配列をシャッフルする話をみて、なるほどな～と思いつつも、よくよく考えてみるとこれは2つの意味で駄目です。 1. 計算量が O(n * log(n)) であること。 2. ランダムにシャッフルできない。 1. は説明するまでもないので、2の理由を考えてみます。 まず、rand() が 0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。 実際に k = 2, n = 2 の場合を考えて見ましょう。この場合、サイズ2の配列をシャッフルするんですから、 要素を入れ替える場合と入れ替えない場合が 1/2 の確率で出現するのが正しいシャッフルです。 k =

[agw]

素晴らしい解説。

[taninsw]

シュワルツ変換&ソートによるシャフルはランダムじゃない(ただし実用上は問題がない)&ソートだからO(n log(n))なので遅い、という話

[HeavyFeather]

問題点の指摘

[odz]

sortでシャッフルするのはダメという話