Perché ricevo dups con random.shuffle in Python?

Question

Per una lista di 10 interi, ci sono 10! eventuali ordini o permutazioni. Perché il random.shuffle dare duplicati dopo solo 5000 tentativi?

>>> 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, se la probabilità di non avere due la stessa cosa per una singola coppia è: p = (10 - 1) / 10! e il numero di combinazioni è: C = 5000! / 4998! * 2! = 5000 * 4999/2 allora la probabilità di avere un duplicato è:

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

Answer 1

Si chiama Compleanno Paradox .

In base a questa formula da Wikipedia:

ma sostituendo 365 con 10! si avrebbe solo bisogno di circa 2200 esemplari di avere una probabilità del 50% di una collisione, e si sono molto al di sopra che.

Answer 2

Perché è ... casuale! Se si desidera che tutte le permutazioni basta usare itertools.permutations.

Answer 3

forse perché è casuale? Casuale non significa non ripetere, vuol dire che è casuale, il che significa che in teoria potrebbe restituire la stessa risposta esatta ogni volta, non è probabile ma possibile.