■random.shuffleの話 [Python]

かなり小さい len(x) であっても、 x の順列はほとんどの乱数生成器の周期よりも大きくなるので注意してください; このことは長いシーケンスに対してはほとんどの順列は生成されないことを意味します。

9.6. random - 擬似乱数を生成する - Python 2.7ja1 documentation

どういうことだろう?

例えば乱数の周期が5しかないとする。この乱数で要素5の配列をシャッフルする。
[4, 2, 3, 5, 1]
とでた。
まあシャッフルされたっぽい。
繰り返してみる。
[2, 3, 5, 1, 4]
[5, 1, 4, 2, 3]
[4, 2, 3, 5, 1]
[1, 4, 2, 3, 5]
[5, 1, 4, 2, 3]
という感じで出てきた。
順列組み合わせは5!あるはずだが、[4, 2, 3, 5, 1, 4, 2, 3, 5] の部分列5種類しか出てこない。

こういうことが起きるって話か。

ところで「かなり小さい len(x)」っていったいどのぐらいだろう?

Python は中心となる乱数生成器として Mersenne Twister を使います。これは 53 ビットの浮動小数点を生成し、周期が 2**19937-1、本体は C で実装されていて、高速でスレッドセーフです。

9.6. random - 擬似乱数を生成する - Python 2.7ja1 documentation

周期は2**19937-1だそうだ。
桁数だけ評価する
\(\log_{10}~2^{19937}~+~1=~19937~\times~\log_{10}~2~+~1\) ですな。

import math
19937*math.log10(2)+1=6002.635023552793

まあ、6002桁ぐらい*1。

順列組み合わせが6002桁ぐらいになる配列。

math.log10(math.factorial(2081)) #=> 6003.615625445271

このへんか。
2000個程度の配列から上はrandom.shuffle()は十分にランダムではない。
実際は、もっと小さな配列からrandom.shuffle()の結果に周期性が入り込んでくるはずだ。