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

Question

对于一个包含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

编辑：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

- telliott99

---

这是您的答案：<joke> http://xkcd.com/221/ </joke>。 - Madi D.

由于生日悖论（请谷歌一下），仅从N个可能性中选择N**0.5个项目，存在高概率的重复。在这里，N=10！可以预测大约1900次尝试后出现重复项。请查看https://dev59.com/NnI95IYBdhLWcg3w2R3z#2124365获得避免重复的代码。 - Beni Cherniavsky-Paskin

谢谢大家。我其实知道生日悖论，但忽略了它。我并没有意识到N**0.5取决于获得50%重复的机会。 - telliott99

Answer 1

这被称为生日悖论。

根据维基百科上的公式：

但是，如果你用 10! 替换 365，你只需要大约 2200 个示例就有 50% 的概率发生碰撞，而你已经远远超过这个数量。

- Mark Byers

---

如果你计算一下，就会发现在从3628800个元素中选取5000个时，只有大约3%的机会得到5000个不同的值。因此，构建一个结果集时有97%的可能性会得到少于5000个值。 - Autoplectic

Answer 2

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

- Alex Gaynor

Answer 3

也许是因为它是随机的？随机并不意味着不会重复，而是表示它是随机的，从理论上讲，它每次都可能返回完全相同的答案，虽然不太可能，但有可能。

- user177800

---

这就是随机性的问题；你永远无法确定！ - lprsd