Почему я получаю дупс с random.shuffle в Python?

Question

Для списка из 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

Edit: FWIW, если вероятность не иметь два одинаковых для одной пары: р = (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

Это называется парадокс дня рождения .

Согласно этой формуле из Википедии:

, но заменив 365 на 10!, вам понадобится всего около 2200 примеров, чтобы иметь вероятность столкновения 50%, и вы намного выше этого.

Answer 2

Потому что это ... случайно! Если вы хотите все перестановки, просто используйте itertools.permutations.

Answer 3

может быть, потому что это СЛУЧАЙНО? Случайный не означает, что не повторяется, это означает, что это СЛУЧАЙНЫЙ, что означает, что теоретически он может возвращать один и тот же ответ каждый раз, не вероятно, но возможно.