¿Por qué recibo dups con random.shuffle en Python?
-
22-09-2019 - |
Pregunta
Para obtener una lista de 10 enteros, hay 10! posibles órdenes o permutaciones. ¿Por qué dar random.shuffle duplicados después de sólo 5.000 intentos?
>>> 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 probabilidad de no tener dos el mismo para un solo par es: p = (10 - 1) / 10! y el número de combinaciones es: C = 5000! / 4998! * 2! = 5000 * 4999/2 entonces la probabilidad de tener un duplicado es:
>>> import math
>>> f = math.factorial(10)
>>> p = 1.0*(f-1)/f
>>> C = 5000.0*4999/2
>>> 1 - p**C
0.96806256495611798
Solución
Se llama el cumpleaños Paradoja .
De acuerdo con esta fórmula de Wikipedia:
pero sustituyendo 365
con 10!
sólo necesitaría unos 2.200 ejemplos para tener una probabilidad del 50% de una colisión, y que están muy por encima de eso.
Otros consejos
Debido a que es ... al azar! Si desea que todas las permutaciones sólo tiene que utilizar itertools.permutations.
tal vez porque es al azar? Aleatoria no significa no se repite, significa que es al azar, lo que teóricamente significa que podría devolver la exacta misma respuesta cada vez, no es probable pero posible.