首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >为什么这个简单的混洗算法会产生有偏差的结果?一个简单的原因是什么?

为什么这个简单的混洗算法会产生有偏差的结果?一个简单的原因是什么?
EN

Stack Overflow用户
提问于 2009-05-13 17:18:26
回答 12查看 11.1K关注 0票数 22

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

代码语言:javascript
复制
# 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;
}

你可以试试..。不使用52,而是使用3(假设只使用3张牌),并运行10,000次并对结果进行汇总,您将看到结果偏向于某些模式……

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

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

代码语言:javascript
复制
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;
}

但问题是...为什么第一种方法,看起来也是完全随机的,会使结果有偏差?

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

EN

回答 12

Stack Overflow用户

回答已采纳

发布于 2009-05-13 20:18:28

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

让我们假设您从序列123开始,然后我们将列举使用相关代码生成随机结果的所有不同方法。

代码语言:javascript
复制
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

现在,第四列数字,即掉期信息之前的一列,包含了最终结果,其中有27种可能的结果。

让我们计算一下每种模式出现的次数:

代码语言:javascript
复制
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

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

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

以下是探索每种可能模式之一的随机性的C#代码:

代码语言:javascript
复制
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);
        }
    }
}

这将输出以下内容:

代码语言:javascript
复制
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4

所以,虽然这个答案实际上很重要,但它不是一个纯粹的数学答案,你只需要评估随机函数可以达到的所有可能的方式,并查看最终的输出。

票数 26
EN

Stack Overflow用户

发布于 2009-05-13 17:21:00

请看以下内容:

The Danger of Naïveté (Coding Horror)

让我们以三张纸牌为例来看一下。使用3张牌组,洗牌后只有6种可能的牌组顺序:123, 132, 213, 231, 312, 321.

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

对于第二种算法,有6种可能的结果精确地映射到6种可能的“真实”洗牌结果,并且随着时间的推移,它们都应该被平等地表示。

这一点很重要,因为在第一个算法中过度表示的存储桶不是随机的。为偏差选择的桶是可重复和可预测的。因此,如果你正在构建一个在线扑克游戏,并使用第一种算法,黑客可能会发现你使用了朴素的排序,并由此得出某些牌面排列比其他牌组更有可能发生。然后,他们可以相应地下注。他们会失去一些,但他们会赢得比失去的多得多,很快就会让你破产。

票数 38
EN

Stack Overflow用户

发布于 2009-05-13 20:52:11

从你对其他答案的评论中,似乎你不仅想要一个解释为什么分布不是均匀分布的解释(对于这个均匀分布,可除性答案是一个简单的),而且还想要一个“直观”的解释,为什么它实际上是远离均匀分布()。

这是一种看待它的方式。假设您从初始数组[1, 2, ..., n] (其中n可能是3、52或其他任何值)开始,并应用两种算法中的一种。如果所有的排列都是均匀可能的,那么1留在第一个位置的概率应该是1/n。事实上,在第二个(正确的)算法中,它是1/n,因为当且仅当它没有第一次被交换时,1才会留在它的位置上,即,如果对rand(0,n-1)的初始调用返回0。

然而,在第一(错误)算法中,仅当第一次或任何其他时间- i.e都没有交换时,1才保持不变,仅当第一个rand返回0并且其他rands都没有返回0,其概率是( 1/n ) * (1-1/n)^(n-1)≈1/(ne)≈0.37/n,而不是1/n。

这就是“直观”的解释:在你的第一个算法中,较早的项目比较晚的项目更有可能被交换到不合适的位置,所以你得到的排列偏向于这样的模式,即较早的项目在其原始位置是而不是。

(这比这更微妙,例如,1可以被交换到更晚的位置,但通过一系列复杂的交换,最终仍然被交换回原来的位置,但这些概率相对较小。)

票数 22
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/859253

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档