Warum bin ich dups mit random.shuffle in Python zu bekommen?

Question

Eine Liste von 10 ints gibt es 10! möglich Aufträge oder Permutationen. Warum funktioniert random.shuffle geben Duplikate bereits nach 5000 versucht?

>>> 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, wenn die Wahrscheinlichkeit nicht zwei für ein einzelnes Paar das gleiche aufweist, ist: p = (10 - 1) / 10! und die Anzahl von Kombinationen ist: C = 5000! / 4998! * 2! = 5000 * 4999/2 dann ist die Wahrscheinlichkeit, ein Duplikat zu haben, ist:

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

Answer 1

Es nennt sich die Geburtstag Paradox .

Nach dieser Formel aus Wikipedia:

aber ersetzen 365 mit 10! würden Sie nur etwa 2200 Beispiele benötigen eine 50% ige Chance einer Kollision zu haben, und Sie sind viel darüber.

Answer 2

Weil es ... zufällig! Wenn Sie alle Permutationen wollen nur itertools.permutations verwenden.

Answer 3

vielleicht, weil zufällig? Zufällige bedeutet nicht, nicht wiederholt, es bedeutet, dass es zufällig ist, die Mittel theoretisch könnte es genau die gleiche Antwort jedes Mal zurückgeben, nicht wahrscheinlich, aber möglich.