シャッフリングのためにlist.sort(rand)したらうまくいかなかった話

Python

流れ

  • Pythonでsort by randomしようとしたら偏りが出てうまくいかなかった。
  • シャッフルの偏りはsortの実装に依存しているらしい。
  • Rubyではsort_by{rand}すれば「ちゃんと」シャッフルできるっていう話じゃなかったっけ？
  • シュワルツ変換というものがあるらしい。
  • シュワルツ変換でも厳密にはシャッフルできていないらしい。
  • 実用上はやはりFisher-Yatesでいい。

うまく行かなかった話

配列をシャッフルする一つの方法として、ソート関数にランダムに-1,0,1を返す比較関数を渡す、というものが知られている。
Pythonではリストに組み込まれているsortメソッドにcmp関数を渡すことができる。
よって次のように書けばシャッフルできるのではないかと考えた。

import random
ls = range(10)
rand = lambda a,b:random.randint(-1, 1)
ls.sort(rand)
print ls
# => [0, 6, 1, 2, 9, 7, 3, 4, 5, 8]

ところがこのシャッフルは実は全然うまくいっていない。range(1000)をこの方法でシャッフルした結果は以下のように偏っている。

どうもこの偏りはsort関数の実装によって変わってくるらしい。

ランダムソート(笑)とは - 西尾泰和のはてなダイアリー

RubyのArray#sort_by{rand}はシュワルツ変換という方法でシャッフルしている

さて、ここで唐突にRubyにおいてはArray#sort_by{rand}という方法でシャッフリングができた、というかできると言われていたことを思い出す。あのテクニックはどういう根拠でシャッフリングされていることが保証されているのだろうと思い調べてみると、以下の様な記事に突き当たった。

配列のシャッフルの決まり文句は「sort_by{ rand }」だった - (rubikitch loves (Emacs Ruby CUI Books))

どうやらシュワルツ変換という方法でシャッフリングを行なっているからよい、ということらしい。
この方法はあらかじめ配列の分だけ乱数を用意して、それを基準にソートするというもの。
なるほどこの方法は直感的にうまく行きそうだと思う。
Pythonで書いてみた。

import random
from matplotlib import pyplot as plt

ls = range(1000)
randlist = [random.random() for _ in range(1000)]
C = [_ for _ in zip(randlist, ls)]
C.sort()
ls = zip(*C)[1]
plt.plot(range(1000), ls)
plt.show()

実行結果は次のようになる。

おー、よく混ざってる。

シュワルツ変換では厳密にはシャッフルできていない

が、実はこの方法ではダメということが以下で指摘されている。
きまぐれ日記: Schwartzian Transform でランダムシャッフル

まず、rand() が　0..k-1 までの k種類の整数から 1 つ数値を返すものとします。配列のサイズが n の場合、 weightの並びの場合の数は k^n 通り存在します。ところが、配列の順列の場合の数は n! です。 ここで何か矛盾点があるように思えてきます。

うーん、ちょっと難しい。

結局Fisher-Yates

Pythonで数値のリストをシャッフルしたいときは、random.shuffleを使えばよい。

import random
ls = range(10)
random.shuffle(ls)
print ls
# => [7, 5, 3, 6, 1, 9, 8, 0, 2, 4]

ちなみにrandom.shuffleの実装はFisher-Yatesアルゴリズムである。計算量もO(N)なので高速。

    def shuffle(self, x, random=None, int=int):
        """x, random=random.random -> shuffle list x in place; return None.

        Optional arg random is a 0-argument function returning a random
        float in [0.0, 1.0); by default, the standard random.random.
        """

        if random is None:
            random = self.random
        for i in reversed(xrange(1, len(x))):
            # pick an element in x[:i+1] with which to exchange x[i]
            j = int(random() * (i+1))
            x[i], x[j] = x[j], x[i]

m(__)m

ここまで引用したリンクを総括したページはすでにあるのです。

sort_by{rand}はちゃんとshuffleできてるのか - hogeなlog

シュワルツ変換まで書いたあたりで気づいたのだけど、途中まで書いた記事を破棄するのも嫌なのでしれっと公開します。