피셔가 왜 가장 유용한 셔플 알고리즘을 사용합니까?

Question

현대 버전의 fisher yates가 가장 편향적 인 셔플 알고리즘이라고 할 수 있겠습니까? 배열의 각 요소가 원래 자리에 1/n 확률이 있다고 설명 하시겠습니까?

Answer 1

제 (현대, 일명 "크 누스 ') Fisher–Yates 셔플입니다

• 시간과 O를 위해
• 매우 효율적인 O (n)을 구현하는 비교적 간단한 (1) 또는 실제로 O (0) 공간
• 편파 (모든 순열은 동일 확률 임)
• 잘 알려져 있거나 잘 알려져 있으며, 입증 된 바 있습니다.

다른 알고리즘에서 원하는 것은 무엇입니까? (물론, 순열 수가 커지면 다른 것을 시도 할 수도 있지만 대부분의 경우 이러한 거대한 계산을 포함하지 않습니다)?

편집 : 은 그냥이 답변은 질문이 아니라 그 내용의 제목에 응답 것으로 나타났습니다. 특정 RNG는 알고리즘을 구현하는 데 사용으로 간단히 말해서
가, 셔플은 무작위 될 것입니다 (이 질문이 두 부분이 더 일치 할 필요가 좋은 이유 어떤 ...)입니다.
직관적 인 설명은 m 요소가있는 배열의 경우 루프의 감소 제어 변수가 1로 내려 가더라도 위치 n에있는 셀이 감소 할 수있는 가능한 셀,이 매우 세포가 쉽게 같은 비율로 증가 이동되었습니다. 즉, 배열의 마지막 요소는 배열의 어느 위치에서나 끝날 수 있지만 첫 번째 반복에서 이동할 수있는 기회는 단 한 번뿐입니다. 이동할 두 번째 요소부터 마지막 ​​요소까지 이동해야 할 곳이 하나 더 적지 만 1/m의 확률로 첫 번째 반복 과정에서 쉽게 이동할 수 있습니다.

Answer 2

완벽한 의사 난수 생성기 (Mersenne Twister 매우 가깝습니다)가 주어지면 Fisher-Yates 알고리즘은 모든 순열이 동일한 확률로 발생한다는 점에서 완전히 편파적입니다. 이것은 유도를 사용하여 증명하기 쉽습니다. 피셔 - 예이츠 알고리즘 (파이썬 구문 의사 코드)은 다음과 같이 반복적으로 기록 될 수있다 :

def fisherYatesShuffle(array): 
    if len(array) < 2: 
     return 

    firstElementIndex = uniform(0, len(array)) 
    swap(array[0], array[firstElementIndex]) 
    fisherYatesShuffle(array[1:]) 

각 인덱스 firstElementIndex로서 선택되는 동일한 확률을 갖는다. 당신이 재귀 할 때, 당신은 지금 여전히 남아있는 요소를 선택할 확률이 같습니다.

편집 : 알고리즘 수학적 편견 것으로 입증되었습니다. 알고리즘이 비 결정적이므로 구현이 올바르게 작동하는지 테스트하는 가장 좋은 방법은 통계적입니다. 나는 임의적이지만 작은 크기의 배열을 취해서 여러 번 차례로 섞어서 (각 입력과 동일한 순열로 시작) 각 출력 순열이 발생하는 횟수를 계산합니다. 그런 다음 Pearson's Chi-square Test을 사용하여이 분포를 균일하게 테스트하십시오.