4

我一直在做一些休闲假期计算。我的小项目是模拟意大利的“tomboli”游戏。一个关键的组成部分是对以下过程的模拟；

游戏由一个人控制，他拿着一袋90颗弹珠，编号从1到90。他从袋子里随机抽出一颗弹珠，每次向玩家喊出弹珠编号。

经过一番思考，我为这个构建块编写了以下代码；

// NBR marbles, numbered 1...NBR are in a bag. Simulate randomly
//  pulling them from the bag, one by one, until the bag is empty
void bag( int random_sequence[NBR] )
{
    int i;

    // Store each marble as it is pulled out
    int *store = random_sequence;

    // Array of marbles still in the bag
    int not_yet_pulled[NBR];
    for( i=0; i<NBR; i++ )
        not_yet_pulled[i] = i+1;    // eg NBR=90; 1,2,3 ... 90

    // Loop pulling marbles from the bag, one each time through
    for( i=NBR; i>=1; i-- )
    {
        int x = rand();
        int idx = x%i;  // eg i=90 idx is random in range 0..89
                        // eg i=89 idx is random in range 0..88
                        //            ...
                        // eg i=1  idx is random in range 0..0
                        //    (so we could optimize when i=1 but not worth the bother)
        *store++  = not_yet_pulled[idx];

        // Replace the marble just drawn (so it cannot be pulled again)
        //     with the last marble in the bag. So;
        //     1) there is now one less marble in the bag
        //     2) only marbles not yet pulled are still in the bag
        // If we happened to pull the last marble in the *current subarray*, this is
        //    not required but does no harm.
        not_yet_pulled[idx] = not_yet_pulled[i-1];
    }
}

我知道在随机数的游戏模拟中到处都是微妙之处和陷阱，所以虽然我对我的代码很满意，但我的信心还不到 100%。所以我的问题是；

1）我的代码有什么问题吗？

2) [如果 1) 的答案是否定的] 我是否在不知不觉中使用了标准洗牌算法？

3) [如果 2) 的答案是否定的] 我的算法与标准替代方案相比如何？

编辑 感谢所有回答的人。我将接受 Aidan Cully 的回答，因为事实证明我正在重新发现 Fisher-Yates 算法，并揭示了问题的核心。当然，我可以通过预先进行一些研究来节省自己的时间和精力，这并不奇怪。但另一方面，这是一个有趣的爱好项目。其余的模拟都是例行公事，这是最有趣的部分，如果我自己不去，我会剥夺自己的乐趣。此外，我试图模拟一个人从袋子里取出弹珠，但在我意识到这种情况与洗牌完全相似的时候已经很晚了。

另一个有趣的地方是有一个小缺陷，由 Ken 指出，经常重复的模式 rand()%N 并不是从 0..N-1 范围内选择随机数的好方法。

最后，我的Fisher-Yates 版本缺乏优雅的技巧，它允许就地改组的良好特性。结果，我的算法会以同样随机但反向的洗牌告终。

4

8 回答 8

11

使用Fisher-Yates-Knuth 洗牌：

public static void shuffle(int[] array) 
{
    Random rng = new Random();       // java.util.Random.
    // n is the number of items left to shuffle
    for (int n = array.length; n > 1; n--) 
    {
        // Pick a random element to move to the end
        int k = rng.nextInt(n);  // 0 <= k <= n - 1.
        // Simple swap of variables
        int tmp = array[k];
        array[k] = array[n - 1];
        array[n - 1] = tmp;
    }
}

看起来您的代码可能有效，但我不确定。它比标准算法更模糊。

于 2009-12-28T23:00:07.523 回答
7

您正在使用Fisher-Yates shuffle algorithm。

于 2009-12-28T22:58:43.797 回答
7 
int idx = x%i;  // eg i=90 idx is random in range 0..89

它在那个范围内，但不是均匀分布的，除非 90（或 NBR）除以 max(rand())。如果您使用的是 2 位计算机，那可能不是真的。例如，在这里，idx 为 0 的可能性略高于为 89。

于 2009-12-28T23:13:48.043 回答
2

rand() % i将具有更好的接近均匀分布（以牺牲性能为代价）的替代方案是(int) ((rand() / (double) (RAND_MAX+1)) * i).

或者，使用已知效果良好的伪随机数生成算法，例如Mersenne twister。

于 2009-12-28T23:57:19.453 回答
2

分析算法以检查它们是否真的是随机的非常困难。
除了具有大学数学水平的人（或者像美国人所说的那样，数学专业）之外，这远远超出了大多数人的技能，甚至无法验证。

因此，您应该尝试使用已经构建的算法。
你看过std::random_shuffle()吗？

 void bag( int random_sequence[NBR] )
 {
     for(int i=0; i<NBR; ++i) 
     {    random_sequence[i] = i+1;
     }
     std::random_shuffle(random_sequence,random_sequence + NBR);
 }

引用 std::random_shuffle() 页面：

该算法在 Knuth 的第 3.4.2 节中进行了描述（DE Knuth，计算机编程的艺术。第 2 卷：半数值算法，第二版。Addison-Wesley，1981）。Knuth 归功于 Moses and Oakford (1963) 和 Durstenfeld (1964)。注意有N！排列 N 个元素的序列的方法。Random_shuffle 产生均匀分布的结果；也就是说，任何特定排序的概率都是 1/N!。这条评论很重要的原因是有许多算法乍一看似乎可以实现序列的随机混洗，但实际上并不能在 N 上产生均匀分布！可能的订购。也就是说，很容易随机洗牌错误。

于 2009-12-28T23:03:00.600 回答
1

只是几个风格点：

  1. 您对具有给定长度的数组的签名可能会让人产生这样的错觉，即编译器保证该参数至少包含 IDX 元素。它不是。
  2. 我可能会给第二个 for 循环中的循环索引一个更具描述性的名称，例如 marblesRemaining，这样它是什么就更清楚了，不需要通过注释来解释。它还将它与它在第一个循环中的完全不同的用途分开。
于 2009-12-28T23:12:47.780 回答
1

除了对随机数生成的争论之外，您的随机播放算法看起来是正确的。

不过，您可以改进它：稍加思考，您可以看到您可以将数字随机排列。因此，您可以只使用输出缓冲区，而不是分配临时数组。

于 2009-12-29T06:54:48.353 回答
0

正如其他人已经评论的那样，使用经过验证的洗牌算法。

值得注意的是，您的 C/C++ 库仅提供一个伪随机数。

需要高可靠性随机化算法的系统使用专用硬件来生成随机数。高端扑克网站就是一个很好的例子。例如，参见Pokerstars关于他们的随机数生成技术的文章。

Netscape 加密的早期版本被破解，因为黑客能够预测所使用的“随机”数字，因为伪随机数字生成器是用当前时间播种的。请参阅Wikipedia 上的这篇文章。

于 2009-12-28T23:12:18.630 回答