4

10 個の int のリストには、10 個あります。可能な順序または順列。5000回試行しただけでrandom.shuffleが重複するのはなぜですか?

>>> L = range(10)
>>> rL = list()
>>> for i in range(5000):
...     random.shuffle(L)
...     rL.append(L[:])
... 
>>> rL = [tuple(e) for e in rL]
>>> len(set(rL))
4997
>>> for i,t in enumerate(rL):
...     if rL.count(t) > 1:
...         print i,t
... 
102 (7, 5, 2, 4, 0, 6, 9, 3, 1, 8)
258 (1, 4, 0, 2, 7, 3, 5, 9, 6, 8)
892 (1, 4, 0, 2, 7, 3, 5, 9, 6, 8)
2878 (7, 5, 2, 4, 0, 6, 9, 3, 1, 8)
4123 (5, 8, 0, 1, 7, 3, 2, 4, 6, 9)
4633 (5, 8, 0, 1, 7, 3, 2, 4, 6, 9)
>>> 10*9*8*7*6*5*4*3*2
3628800
>>> 2**19937 - 1
431542479738816264805523551633791983905393 [snip]

>>> L = list()
>>> for i in range(5000):
...     L.append(random.choice(xrange(3628800)))
... 
>>> len(set(L))
4997

編集: FWIW、1 つのペアに対して 2 つの同じものがない確率が次の場合: p = (10! - 1) / 10! 組み合わせの数は: C = 5000! / 4998! ※2！= 5000 * 4999 / 2 重複する確率は次のとおりです。

>>> import math
>>> f = math.factorial(10)
>>> p = 1.0*(f-1)/f
>>> C = 5000.0*4999/2
>>> 1 - p**C
0.96806256495611798
4

3 に答える 3

19

それは誕生日のパラドックスと呼ばれています。

ウィキペディアのこの式によると：

しかし、あなたに置き換える365と10!、衝突の可能性が 50% になるのに必要な例は約 2200 だけであり、あなたはそれをはるかに上回っています。

于 2010-01-23T21:22:06.780 に答える
6

それは…ランダムだからです！すべての順列が必要な場合は、itertools.permutations を使用してください。

于 2010-01-23T21:15:35.103 に答える
2

たぶんランダムだから？ランダムとは繰り返さないという意味ではなく、ランダムであることを意味します。つまり、理論的には毎回まったく同じ答えを返す可能性があり、可能性は低いですが可能です。

于 2010-01-23T21:18:38.390 に答える