Pourquoi ai-je dups avec random.shuffle en Python?
-
22-09-2019 - |
Question
Pour une liste de 10 ints, il y a 10 ans! ordres possibles ou permutations. Pourquoi ne donne random.shuffle les doublons après seulement 5000 essais?
>>> 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, si la probabilité de ne pas avoir deux la même pour une seule paire est la suivante: p = (10 - 1) / 10! et le nombre de combinaisons est: C = 5000! / 4998! * 2! = 5000 * 4999/2 alors la probabilité d'avoir un double est:
>>> import math
>>> f = math.factorial(10)
>>> p = 1.0*(f-1)/f
>>> C = 5000.0*4999/2
>>> 1 - p**C
0.96806256495611798
La solution
Il est appelé anniversaire Paradox .
Selon cette formule de Wikipedia:
mais en remplaçant 365
avec 10!
vous ne besoin d'environ 2200 exemples pour avoir une chance de 50% d'une collision, et vous êtes ainsi au-dessus.
Autres conseils
Parce qu'il est ... au hasard! Si vous voulez que toutes les permutations utiliser juste itertools.permutations.
peut-être parce est aléatoire? Au hasard ne veut pas dire ne se répète pas, cela signifie qu'il est aléatoire, ce qui signifie théoriquement il pourrait revenir exactement la même réponse à chaque fois, peu probable mais possible.