为什么这个简单的shuffle算法产生有偏差的结果？什么是一个简单的原因？

it seems that this simple shuffle algorithm will produce biased results:

似乎这个简单的shuffle算法会产生偏差的结果:

# suppose $arr is filled with 1 to 52

for ($i < 0; $i < 52; $i++) { 
  $j = rand(0, 51);

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

you can try it... instead of using 52, use 3 (suppose only 3 cards are used), and run it 10,000 times and tally up the results, you will see that the results are skewed towards certain patterns...

你可以尝试...而不是使用52,使用3(假设只使用3张卡),并运行10,000次并计算结果,你会看到结果偏向某些模式......

the question is... what is a simple explanation that it will happen?

问题是......它会发生什么简单的解释?

the correct solution is to use something like

正确的解决方案是使用类似的东西

for ($i < 0; $i < 51; $i++) {  # last card need not swap 
  $j = rand($i, 51);        # don't touch the cards that already "settled"

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

but the question is... why the first method, seemingly also totally random, will make the results biased?

但问题是......为什么第一种方法,似乎也是完全随机的,会使结果产生偏差?

Update 1: thanks for folks here pointing out that it needs to be rand($i, 51) for it to shuffle correctly.

更新1:感谢这里的人们指出它需要rand($ i,51)才能正确地进行洗牌。

12 个解决方案

#1

Here's the complete probability tree for these replacements.

这是这些替换的完整概率树。

Let's assume that you start with the sequence 123, and then we'll enumerate all the various ways to produce random results with the code in question.

让我们假设您从序列123开始,然后我们将枚举所有各种方法来生成随机代码的相关代码。

123
 +- 123          - swap 1 and 1 (these are positions,
 |   +- 213      - swap 2 and 1  not numbers)
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 123      - swap 2 and 2
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 132      - swap 2 and 3
 |       +- 231  - swap 3 and 1
 |       +- 123  - swap 3 and 2
 |       +- 132  - swap 3 and 3
 +- 213          - swap 1 and 2
 |   +- 123      - swap 2 and 1
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 213      - swap 2 and 2
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 231      - swap 2 and 3
 |       +- 132  - swap 3 and 1
 |       +- 213  - swap 3 and 2
 |       +- 231  - swap 3 and 3
 +- 321          - swap 1 and 3
     +- 231      - swap 2 and 1
     |   +- 132  - swap 3 and 1
     |   +- 213  - swap 3 and 2
     |   +- 231  - swap 3 and 3
     +- 321      - swap 2 and 2
     |   +- 123  - swap 3 and 1
     |   +- 312  - swap 3 and 2
     |   +- 321  - swap 3 and 3
     +- 312      - swap 2 and 3
         +- 213  - swap 3 and 1
         +- 321  - swap 3 and 2
         +- 312  - swap 3 and 3

Now, the fourth column of numbers, the one before the swap information, contains the final outcome, with 27 possible outcomes.

现在,第四列数字,即交换信息之前的数字,包含最终结果,有27种可能的结果。

Let's count how many times each pattern occurs:

让我们计算每个模式出现的次数:

123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

If you run the code that swaps at random for an infinite number of times, the patterns 132, 213 and 231 will occur more often than the patterns 123, 312, and 321, simply because the way the code swaps makes that more likely to occur.

如果运行随机交换无限次的代码,则模式132,213和231将比模式123,312和321更频繁地发生,这仅仅是因为代码交换的方式使得更可能发生。

Now, of course, you can say that if you run the code 30 times (27 + 3), you could end up with all the patterns occuring 5 times, but when dealing with statistics you have to look at the long term trend.

现在,当然,你可以说,如果你运行代码30次(27 + 3),你最终可能会出现5次所有模式,但在处理统计数据时,你必须看看长期趋势。

Here's C# code that explores the randomness for one of each possible pattern:

这是C#代码,它探索了每种可能模式之一的随机性:

class Program
{
    static void Main(string[] args)
    {
        Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
        {
            { "123", 0 },
            { "132", 0 },
            { "213", 0 },
            { "231", 0 },
            { "312", 0 },
            { "321", 0 }
        };

        Char[] digits = new[] { '1', '2', '3' };
        Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
        {
            Char[] result = new Char[] { input[0], input[1], input[2] };
            Char temp = result[pos1];
            result[pos1] = result[pos2];
            result[pos2] = temp;
            return result;
        };

        for (Int32 index1 = 0; index1 < 3; index1++)
        {
            Char[] level1 = swap(digits, 0, index1);
            for (Int32 index2 = 0; index2 < 3; index2++)
            {
                Char[] level2 = swap(level1, 1, index2);
                for (Int32 index3 = 0; index3 < 3; index3++)
                {
                    Char[] level3 = swap(level2, 2, index3);
                    String output = new String(level3);
                    occurances[output]++;
                }
            }
        }

        foreach (var kvp in occurances)
        {
            Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
        }
    }
}

This outputs:

So while this answer does in fact count, it's not a purely mathematical answer, you just have to evaluate all possible ways the random function can go, and look at the final outputs.

因此,虽然这个答案确实可以计算,但这不是一个纯数学答案,你只需要评估随机函数可以采用的所有可能方法,并查看最终输出。

#2

See this:
The Danger of Naïveté (Coding Horror)

看到:Naïveté的危险(编码恐怖)

Let's look at your three card deck as an example. Using a 3 card deck, there are only 6 possible orders for the deck after a shuffle: 123, 132, 213, 231, 312, 321.

让我们看一下你的三张牌组。使用3张牌组,洗牌后甲板上只有6种可能的订单:123,132,213,231,312,321。

With your 1st algorithm there are 27 possible paths (outcomes) for the code, depending on the results of the rand() function at different points. Each of these outcomes are equally likely (unbiased). Each of these outcomes will map to the same single result from the list of 6 possible "real" shuffle results above. We now have 27 items and 6 buckets to put them in. Since 27 is not evenly divisible by 6, some of those 6 combinations must be over-represented.

使用第一个算法,代码有27种可能的路径(结果),具体取决于不同点的rand()函数的结果。这些结果中的每一个都是同等可能的(无偏见的)。这些结果中的每一个都将映射到上面6个可能的“真实”混洗结果列表中的相同单个结果。我们现在有27个项目和6个桶用于放入它们。由于27个不能被6整除,因此这6个组合中的一些必须过度表示。

With the 2nd algorithm there are 6 possible outcomes that map exactly to the 6 possible "real" shuffle results, and they should all be represented equally over time.

使用第二种算法,有6种可能的结果可以准确地映射到6种可能的“真实”混洗结果,并且它们应该随时间平均表示。

This is important because the buckets that are over-represented in the first algorithm are not random. The buckets selected for the bias are repeatable and predictable. So if you're building an online poker game and use the 1st algorithm a hacker could figure out you used the naive sort and from that work out that certain deck arrangements are much more likely to occur than others. Then they can place bets accordingly. They'll lose some, but they'll win much more than they lose and quickly put you out of business.

这很重要,因为在第一个算法中过度表示的桶不是随机的。为偏差选择的桶是可重复且可预测的。因此,如果你正在建立一个在线扑克游戏并使用第一种算法,那么黑客可能会发现你使用了天真的排序,并且从那项工作中可以看出某些甲板安排比其他人更容易发生。然后他们可以相应地下注。他们会失去一些,但他们会赢得比失败更多的东西,并迅速让你破产。

#3

From your comments on the other answers, it seems that you are looking not just for an explanation of why the distribution is not the uniform distribution (for which the divisibility answer is a simple one) but also an "intuitive" explanation of why it is actually far from uniform.

根据您对其他答案的评论,您似乎不仅仅想要解释为什么分布不是均匀分布(对于哪个分布是简单的分布),而是对其原因的“直观”解释。实际上远非均匀。

Here's one way of looking at it. Suppose you start with the initial array [1, 2, ..., n] (where n might be 3, or 52, or whatever) and apply one of the two algorithms. If all permutations are uniformly likely, then the probability that 1 remains in the first position should be 1/n. And indeed, in the second (correct) algorithm, it is 1/n, as 1 stays in its place if and only if it is not swapped the first time, i.e. iff the initial call to rand(0,n-1) returns 0.
However, in the first (wrong) algorithm, 1 remains untouched only if it is neither swapped the first time nor any other time — i.e., only if the first rand returns 0 and none of the other rands returns 0, the probability of which is (1/n) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0.37/n, not 1/n.

这是一种看待它的方式。假设您从初始数组[1,2,...,n](其中n可能是3或52或其他)开始,并应用这两种算法中的一种。如果所有排列均匀可能,则1保持在第一位置的概率应为1 / n。事实上,在第二个(正确的)算法中,它是1 / n,当且仅当它第一次没有交换时,1保持在其位置,即iff对rand(0,n-1)的初始调用返回但是,在第一个(错误的)算法中,1只有在第一次或任何其他时间都没有交换时仍然保持不变 - 即,只有当第一个兰特返回0并且其他任何一个都没有返回0时,概率为0这是(1 / n)*(1-1 / n)^(n-1)≈1/(ne)≈0.37/ n,而不是1 / n。

And that's the "intuitive" explanation: in your first algorithm, earlier items are much more likely to be swapped out of place than later items, so the permutations you get are skewed towards patterns in which the early items are not in their original places.

这就是“直观”的解释:在你的第一个算法中,早期的项目比后面的项目更有可能被替换掉,所以你得到的排列倾向于早期项目不在原始位置的模式。

(It's a bit more subtle than that, e.g. 1 can get swapped into a later position and still end up getting swapped back into place through a complicated series of swaps, but those probabilities are relatively less significant.)

(它比这更微妙,例如1可以换成后来的位置,并且最终通过一系列复杂的掉期交换回来,但这些概率相对不太重要。)

#4

The best explanation I've seen for this effect was from Jeff Atwood on his CodingHorror blog (The Danger of Naïveté).

我见过这个效果的最佳解释来自Jeff Atwood的CodingHorror博客(Naïveté的危险)。

Using this code to simulate a 3-card random shuffle...