12

经典的 Fisher Yates 看起来像这样：

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

这个版本是否比第一个版本更差（或更好）？它是否会扭曲结果概率？

4

2 回答 2

4

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

0123 0132 0321 3230                                                                                  2013 2031 2310 3012
                    0213 0231 0312 3210                                          1203 1230 1302 3201
                                        2103 2130 2301 3102  1023 1032 1320 3021

ETC

于 2012-01-14T10:48:31.390 回答
1

对我来说看起来不错（假设 rand() % N 是公正的，但事实并非如此）。似乎应该有可能证明输入的每个排列都是由恰好 1 个随机选择序列产生的，其中每个随机选择都是平衡的。

将此与错误的实现进行比较，例如

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

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

于 2012-01-14T10:58:29.960 回答