费舍尔耶茨变化

经典的费雪耶茨看起来是这样的：费舍尔耶茨变化

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

是这个版本以任何方式更差（或比第一个更好？它是否歪曲了结果概率？

来源

2012-01-14 fredoverflow

假设“更糟”意味着“产生非均匀分布”，对吧？ – 2012-01-14 10:19:46

@ R.MartinhoFernandes：对。 '它是否扭曲了由此产生的概率？' – fredoverflow 2012-01-14 10:21:26

它更像是一个数学问题。 - 作为一个编程问题，你为什么要在C++中实现这个功能？它在标准库（random_shuffle）中。 – UncleBens 2012-01-14 10:35:37

是的它假设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

etc

来源

2012-01-14 10:48:31 Pubby

对我来说看起来不错（假设rand（）％N是无偏的，它不是）。似乎应该有可能证明输入的每个排列都是由随机选择的正好一个序列产生的，其中每个随机选择是平衡的。

比较这与一个错误的实现，如

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

在这里你可以看到，有n ^ň同样可能的方式生产N！排列，并且因为n ⁿ不能被n整除！当n> 2时，这些排列中的一些必须比其他排列更频繁地产生。

来源

2012-01-14 10:58:29 UncleBens

费舍尔耶茨变化

回答

相关问题