이 셔플 링 알고리즘은 균일 한 확률로 각 순열을 생성합니까?

Question

나는 특정 naive shuffling 알고리즘이 어떻게 편향되어 있는지를 보았고, 기본적으로 그것을 얻은 것처럼 느껴졌고 Fischer-Yates 알고리즘이 어떻게 편향되지 않았는지 알게되었습니다. 나는 목록을 뒤섞는 방법을 생각할 때 처음 생각한 다음 알고리즘을 가지고있다. 나는 그것이 두 배의 메모리를 소비하고 불필요하게 많은 시간을 소비한다는 것을 알고 있지만, 균일 한 분포로 각 순열을 생성한다면 여전히 궁금해합니다. 또는 약간의 비열한 이유가 있다면 편향 될 수는 없습니다.

임의의 임의의 셔플에 다른 "바람직하지 않은"속성이 있는지 궁금해합니다. 목록의 여러 위치의 확률이 일부 값에 따라 달라지는 것과 같습니다.

def shuf(x): 
    out = [None for i in range(len(x))] 
    for i in x: 
     pos = rand.randint(0,len(x)-1) 
     while out[pos] != None: 
      pos = rand.randint(0,len(x)-1) 
     out[pos] = i 
    return out 

나는 10^6 시도를 실행하는 20 개의 요소 목록에 대해이 히트 맵을 생성했으며 다음과 같이 생성했습니다. 지도의 (i, j) 좌표는 목록의 i 번째 위치가 원래 목록의 j 번째 요소로 채워질 확률을 나타냅니다. 내가 열 맵에 어떤 패턴이 표시되지 않는 동안 분산이 높을 수 있습니다처럼

, 그것은 보인다. 아니면 최소와 최대가 어딘가에 올라와야하기 때문에 분산을 무시한 히트 맵일 수 있습니다.

Answer 1

바람직하지 않은 특성 - 당신은 큰 세트를 셔플하는 경우이 비용이 많이들 수 있습니다 :

while out[pos] != None: 
      pos = rand.randint(0,len(x)-1) 

상상 렌 (X) == 100,000,000 당신은 이미 90,000,000 배치 한 - 당신은 루프 A를거야 히트 받기 전에.

재미있는 운동 :

1. 의 모양을 열지도는 단순히 (x)를 10E6 반복을 통해 1 렌 사이의 난수를 생성하는 모습입니까?

2. 비교를 위해 Fischer-Yates의 히트 맵은 어떻게됩니까? 눈에서

, 그것은 (피셔 - 예이츠보다 느리게이기는하지만) 저 같은 균일 한 RNG 주어진, 그것은 진정한 무작위 분포를 산출한다 보인다.