왜이 셔플 링 알고리즘이 잘못 되었습니까?

Question

내가 피셔 - 예이츠에 대한 읽기 전에, 이것이 내가 생각 해낸 알고리즘입니다 : 나의 이해에서

def sort(arr): 
    for i in range(len(arr)): 
     swap(arr, i, rand.randint(0, len(arr) - 1)) 

가이 피셔 - 예이츠 사이의 유일한 차이점은 대신 :

swap(arr, i, rand.randint(0, len(arr) - 1)) 

내가 작성해야 :

swap(arr, i, rand.randint(i, len(arr) - 1)) 

사람이 첫 번째 알고리즘은 잘못된 방법을 설명 할 수? (즉, 랜덤 셔플을 생성하지 않음). 위키

Answer 1

는 :

마찬가지로, 각 반복에 유효한 배열 인덱스의 전체 범위에서 항상 선택 J는 분명히 매우 적게 나마 바이어 싱하는 결과를 생성한다. 이것은 스왑의 순차적 인 가능한 시퀀스 인 ⁿ을 생성한다는 사실에서 알 수 있습니다. 반면에 n! n 요소 배열의 가능한 순열 n ⁿ은 n에 의해 균등하게 나눌 수 없기 때문에! n> 2 일 때 (후자는 n과 소수 요소를 공유하지 않는 n-1로 나눌 수 있기 때문에), 일부 순열은 다른 것보다 n ⁿ 개의 스왑 시퀀스를 더 많이 생성해야합니다. 이러한 편향의 구체적인 예로서 3 요소 배열의 셔플 링 결과의 분포를 관찰하십시오 [1, 2, 3]. 이 배열에는 6 가지 가능한 순열이 있지만 알고리즘은 27 개의 가능한 셔플을 생성합니다 (33 = 27). 이 경우, [1, 2, 3], [3,1,2] 및 [3,2,1]은 27 개의 셔플 중 4 개에서 각각 발생하지만 나머지 3 개의 순열은 각각 27 개의 셔플 중 5 개에서 발생합니다. 셔플.

본질적으로 셔플에 약간의 바이어스가 도입되어 일부 순열이 다른 것보다 조금 더 잘립니다. 종종 눈에 띄는 것은 아니지만 일부 민감한 애플리케이션 (예 : 순열에 대한 몬테카를로 시뮬레이션)이 정확한 답변을 생성하지 못할 수 있습니다.