费舍尔·耶茨(Fisher Yates)变化 [英] Fisher Yates variation

问题描述

经典的费舍尔·耶茨(Fisher Yates)看起来像这样:

The classic Fisher Yates looks something like this:

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

昨天，我错误地实现了向后"迭代:

Yesterday, I implemented the iteration "backwards" by mistake:

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

此版本是否比第一个版本差(或更好)?它会歪曲结果概率吗?

Is this version in any way worse (or better) than the first? Does it skew the resulting probabilities?

推荐答案

是的，假设rand()是均匀分布的.我们将通过证明每个输入可以以相等的概率生成每个排列来证明这一点.

Yes it's even distribution assuming rand() is. We will prove this by showing that each input can generate each permutation with equal probability.

N = 2可以很容易地证明. 我们将其绘制为一棵树，其中子代代表每个字符串，您可以通过将逗号后的字符插入最左边的字符串来获得每个字符串.

N=2 can be easily proven. We will draw it as a tree where the the children represent each string you can get by inserting the character after comma into the leftmost string.

  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

For N, we will have every permutations for N-1, and randomly swapping the last character for 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

这种卑鄙的归纳法应该引导您使其分布均匀.

This shitty induction should lead you to it having even distribution.

示例:

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 :(弯曲以帮助阅读)

N=4: (curved to aid reading)

                                                           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

等

这篇关于费舍尔·耶茨(Fisher Yates)变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！