왜 random.shuffle을 사용하여 dups를 파이썬으로 구할 수 있습니까?

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 

편집 : FWIW 두을 갖지 않는 확률은 한 쌍에 대해 동일한 경우 : p = (! 1 - 10)/10! 이고 조합 수는 C = 5000!/4998! * 2! = 5000 * 2분의 4,999 는 중복을 가질 확률은 다음과 같습니다

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

Answer 1

Birthday Paradox이라고합니다. 위키 백과에서이 공식에 따르면

:

하지만 10!으로 365 대체 당신은 충돌의 50 %의 확률로 약 2,200 예를 만 필요하고, 그 위의 방법입니다.

Answer 2

그건 때문에 ... 임의! 모든 순열을 원하면 itertools.permutations를 사용하십시오.

Answer 3

아마 RANDOM입니까? 무작위 란 반복하지 않는다는 것을 의미하지는 않으며, 이론적으로 매번 정확한 답변을 반환 할 수 있음을 의미하는 RANDOM을 의미합니다.