Fisher Yates biến

Question

cổ điển Fisher Yates trông giống như sau:

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

Hôm qua, tôi thực hiện lặp "ngược" do nhầm lẫn:

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)]); 
    } 
} 

Là phiên bản này dưới mọi hình thức tồi tệ hơn (hoặc tốt hơn) so với lần đầu tiên? Liệu nó có làm sai lệch xác suất kết quả không?

Answer 1

Có ngay cả phân phối giả định rand() là. Chúng tôi sẽ chứng minh điều này bằng cách cho thấy rằng mỗi đầu vào có thể tạo ra mỗi hoán vị với xác suất bằng nhau.

N = 2 có thể dễ dàng được chứng minh. Chúng tôi sẽ vẽ nó như là một cây nơi các em đại diện cho mỗi chuỗi bạn có thể nhận được bằng cách chèn ký tự sau dấu phẩy vào chuỗi ngoài cùng bên trái.

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

Đối với N, chúng ta sẽ có tất cả các hoán vị cho N-1, và trao đổi một cách ngẫu nhiên các ký tự cuối cùng cho 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 

cảm ứng shitty này nên dẫn bạn đến nó có thậm chí phân phối.

---

Ví dụ:

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: (cong để hỗ trợ đọc)

              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 

etc

Answer 2

Có vẻ OK với tôi (giả sử rand()% N là không thiên vị, không phải là nó). Có vẻ như nó có thể chứng minh rằng mỗi hoán vị của đầu vào được tạo ra bởi chính xác 1 chuỗi các lựa chọn ngẫu nhiên, trong đó mỗi sự lựa chọn ngẫu nhiên được cân bằng.

Hãy so sánh điều này với một thực hiện bị lỗi, chẳng hạn như

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

đây bạn có thể thấy rằng có n ⁿ cách đều có khả năng để sản xuất n! hoán vị, và kể từ n ⁿ không chia hết cho n! trong đó n> 2, một số hoán vị đó phải được tạo ra thường xuyên hơn những cái khác.