4

对于 10 个整数的列表，有 10 个！可能的顺序或排列。为什么 random.shuffle 仅在 5000 次尝试后给出重复项？

>>> 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，如果一对没有两个相同的概率是：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!需要大约 2200 个示例就有 50% 的碰撞机会，而且你远远超过这个。

于 2010-01-23T21:22:06.780 回答
6

因为它是……随机的！如果您想要所有排列，只需使用 itertools.permutations。

于 2010-01-23T21:15:35.103 回答
2

也许是因为是随机的？随机并不意味着不重复，它意味着它是随机的，这意味着理论上它每次都可以返回完全相同的答案，不太可能但可能。

于 2010-01-23T21:18:38.390 回答