为什么这种简单的洗牌算法会产生偏颇的结果?为什么是一个简单的原因?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (29)

这个简单的洗牌算法似乎会产生偏颇的结果:

# 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,并运行它10,000次并总结结果,将看到结果是偏向于某些模式

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

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

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

为什么第一种方法,似乎也是完全随机的,会使结果有偏差?

提问于
用户回答回答于

假设你从序列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

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

让我们数一数每种模式发生了多少次:

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#代码,它探索了每种可能的模式之一的随机性:

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

这一产出:

123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
用户回答回答于

以三张牌牌为例,使用三张牌牌,洗牌后只有六种可能的订单:123, 132, 213, 231, 312, 321.

使用第一个算法,代码有27条可能的路径(结果),这取决于rand()在不同的地方起作用。这些结果中的每一个都是相同的(不偏不倚的)。每一个结果都将映射到上面列出的6个可能的“真正”洗牌结果列表中相同的单一结果。我们现在有27个项目和6个桶来放置它们。因为27不能被6整除,所以这6种组合中的一些是不均匀的。被夸大了。

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

扫码关注云+社区

领取腾讯云代金券