フィッシャーイエーツ変動

Question

は、古典的なフィッシャーイェーツは、このようなものになります。昨日

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

を、私は誤って「後方」の繰り返しを実装：

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は容易に証明できます。 左の文字列にコンマの後に文字を挿入することによって得られる各文字列を子が表すツリーとして描画します。 Nのために

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-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の場合、それらの置換のいくつかは他よりも頻繁に生成されなければならない。