피셔 예이츠 변화

Question

고전 피셔 예이츠는 다음과 같이 보이는

void shuffle2(std::vector<int>& vec) 
{ 
    int n = vec.size(); 
    for (int i = 1; i < n; ++i) 
    { 
     std::swap(vec[i], vec[rand() % (i + 1)]); 
    } 
} 

어떤 식 으로든 더이 버전 (또는 더 나은) 첫 번째보다? 결과 확률이 왜곡됩니까?

Answer 1

예. 균등 분포라고 가정하면 rand()입니다. 우리는 각 입력이 똑같은 확률로 각 순열을 생성 할 수 있다는 것을 보여줌으로써 이것을 증명할 것입니다.

N = 2는 쉽게 증명할 수 있습니다. 우리는 나무로 그릴 것입니다. 여기에서 어린이는 쉼표 뒤에 문자를 가장 왼쪽 문자열에 삽입하여 얻을 수있는 각 문자열을 나타냅니다.

0,1 //input where 0,1 represent indices 
01 10 //output. Represents permutations of 01. It is clear that each one has equal probability 

은 N을 위해, 우리는 N-1에 대한 모든 순열을해야합니다, 무작위로 그것도 분포를 갖는이 엿 유도는 당신을지도한다 N

(N-1 0th permutation),N  .....   (N-1 Ith permutation),N ________________________ 
    /   \      /     \        \ 
0th permutation of N 1st permutation.... (I*N)th permutation ((I*N)+1)th permutation .... (I*N)+(I-1)th permutation 

의 마지막 문자를 교환.

---

예 :

N = 2 :

0,1 
01 10 // these are the permutations. Each one has equal probability 

N = 3 :

  0,1|2   // the | is used to separate characters that we will insert later 
    01,2   10,2 // 01, 10 are permutations from N-1, 2 is the new value 
210 021 012 201 120 102 // these are the permutations, still equal probability 

N = 4 :

              0,1|23 

                 01,2|3 10,2|3 

              012,3 021,3 210,3 102,3 120,3 201,3 


            1203 1230 1302 3201 
             2103 2130 2301 3102 1023 1032 1320 3021 

(판독을 지원하기 위해 곡선)

등

Answer 2

나에게 잘 보이네요. (rand() % N은 편견이 없다고 가정합니다. 그렇지 않습니다). 입력의 모든 순열이 각각의 무작위 선택이 균형을 이루는 정확히 1 시퀀스의 무작위 선택에 의해 생성된다는 것을 입증 할 수 있어야합니다.

는 n을 생산하는 ^N 똑같이 가능성이 방법은 N이 있음을 볼 수있다 같은

다음

for (int i = 0; i < v.size(); ++i) { 
    swap(v[i], v[rand() % v.size()]); 
} 

등의 결함이 구현이 비교! 순열 및 n 이후 ⁿ n으로 나눌 수 없습니다! n> 2 인 경우, 이러한 순열 중 일부는 다른 것보다 더 자주 생산되어야합니다.