为什么我在Python中使用random.shuffle时会出现重复项？

Question

对于一个包含10个整数的列表，可能的排列方式有10!（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

补充说明：如果考虑到一对数字不重复的概率是： 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

Answer 1

可能是因为是随机的吧？随机并不意味着不会重复，它的意思是随机的，这意味着从理论上讲，它每次都可能返回完全相同的答案，虽然这种情况不太可能发生，但确实是有可能的。

Answer 2

因为它是... 随机的！如果你想要所有的排列组合，可以直接使用 itertools.permutations。

Answer 3

这被称为“生日悖论”。

根据维基百科上的这个公式：

如果把 365 换成 10!，那么你只需要大约2200个例子，就能有50%的机会发生碰撞，而你现在的数量远远超过这个了。