这个洗牌算法有什么问题吗？

Question

我一直在进行一些休闲的计算机操作。我的小项目是模拟意大利游戏“tomboli”。其中一个关键构建块是以下过程的模拟：

游戏由一名手持编号为1至90的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 版本缺乏优雅的技巧，这使得洗牌变得简单易行。因此，我的算法会得到同样随机但是反向的洗牌。

- Bill Forster

---

按手写汇编的方式进行了注释 ;) - Hamish Grubijan

[@HamishGrubijan] 这就是为什么 Bill 值得再次 +1，因为他向一个路人解释了一个新的算法... :-D。顺便提醒一下 Bill，在调用这个方法之前不要忘记 srand(time(0));。 - OmarOthman

@OmarOthman 谢谢你。我记得当时（这是一个旧问题），我在想 Hamish 是在夸我还是批评我。最好假设是夸我 :- ) - Bill Forster

Answer 1

使用 Fisher-Yates-Knuth shuffle算法：

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

看起来你的代码可能是可行的，但我不确定。相比于标准算法，它更加难以理解。

- RossFabricant

---

只是想插一句，Python的random.shuffle()确实使用了Fisher-Yates算法。 - Hamish Grubijan

Fisher-Yates已被证明是公正的，而且它非常简单高效。几乎没有什么理由使用其他方法。 - dsimcha

Answer 2

您正在使用费舍尔耶茨洗牌算法。

- Aidan Cully

---

这基本上是正确的，唯一的区别在于你将其存储到一个新数组中，而 F-Y 算法（例如 rossfabricant 上面所描述的）则将其存储到输入数组末尾的空白部分。 - Edmund

好吧，这不是完全的Fisher-Yates洗牌算法，但它非常接近，你可以合理地说它是，所以我没有理解-1并退回了一些点。 - kriss

@Edmund：实际上FY是一个数学算法，因此没有存储机制的概念。然而，根据Durstenfeld描述的标准实现确实是原地进行的。 - Martin York

Answer 3

int idx = x%i;  // eg i=90 idx is random in range 0..89

这个范围内的分布不是均匀的，除非90（或NBR）可以整除max(rand())。如果你使用的是2位计算机，那么这个条件可能不成立。例如，在这里，idx为0的概率要略高于89。

- Ken

---

好的观点！如果n很小，那么只会有非常轻微的偏差，但是如果你运行足够多的测试，它将是明显的。 - Mark Byers

@Ken：想打赌rand(n)在许多实现中有相同的偏差吗？ - kriss

kriss：消除偏差很容易。例如，可以参考java.util.Random.nextInt(int)。我怀疑在这种情况下实现会产生偏差的数字。 - Joey

Answer 4

分析算法以检查其是否真正随机非常困难。
除了具有大学数学水平（或者按照美国人的说法，数学专业）的人之外，这对于大多数人来说甚至连验证都超出了他们的能力。

因此，您应该尝试使用已经构建好的算法。
您看过 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（D. E. Knuth，《计算机程序设计艺术》第2卷：半数值算法，第二版。Addison-Wesley，1981年）的第3.4.2节中有描述。Knuth归功于Moses和Oakford（1963年）以及Durstenfeld（1964年）。请注意，有N！种排列N个元素序列的方式。Random_shuffle产生均匀分布的结果；也就是说，任何特定排序的概率为1/N！。这条评论之所以重要，是因为存在许多算法，乍一看似乎实现了随机洗牌序列，但实际上并没有产生N！可能的顺序的均匀分布。也就是说，很容易出错。

- Martin York

---

+1，但有三个小问题：1）大学（没有d）。2）我认为这是一个学习练习而不是生产代码。3）我可以看出OP的算法不是真正的随机，因为如果(RAND_MAX + 1) % i != 0（对于大多数i的值可能是真的），rand() % i会偏向较低的结果。 - Chris Lutz

@Chris：你能详细解释一下为什么rand() % i应该偏向于较低的结果，即使RAND_MAX足够大而不是i吗？我相信许多生成器使用LCG等偏差在不选择完整序列的情况下是无法检测到的。 - kriss

@Kriss：是的，差别很小。但重点是它是可测量的，因此引入了基础知识。这就是为什么好的随机文本书会详细解释为什么应该使用“floor(rand()/(RAND_MAX + 1,o) * RANGE)”（虽然还不完美，但比使用模数更好）。但要比这更好需要数学技能，而这限制了我的能力。因此，我更喜欢使用已由具有适当知识和教育背景的人编写的已建立的算法。 - Martin York

@Kriss：我认为一个更简单的答案是：如果RAND_MAX为4，而i为3，则0和1将有40%的时间输出，而2将有20%的时间输出。随着数字变得越来越大，差距会缩小但永远不会达到零。 - Mark Ruzon

Answer 5

一种替代 rand() % i 的方法，它具有更好的近似均匀分布（以性能为代价），是 (int) ((rand() / (double) (RAND_MAX+1)) * i)。

或者，使用已知表现良好的伪随机数生成算法，如梅森旋转算法。

- Carlo

---

不需要将其转换为双精度浮点数。通过添加1.0而不是1，您可以得到一个双精度浮点数。 - Martin York

尽管这只是将转换的语义移到编译器上。在汇编级别上，无论您是否明确编码它或通过添加双精度隐式要求它，转换仍然会发生。 - Eric J.

Answer 6

只有一些风格上的要点：

1. 您使用给定长度的数组作为参数可能会让人误以为编译器保证该参数至少包含IDX个元素。但实际上并不是这样。
2. 我建议在第二个for循环中，将循环索引命名为marblesRemaining，这样更清晰明了，不需要通过注释来解释它的作用。同时也能与第一个循环中完全不同的用途区分开来。

- JohnMcG

---

1. 是的，我意识到了，我只是在最后添加了给定长度作为可执行注释。
2. 很好的观点。我避免和厌恶使用长而无意义的循环计数器名称，但你是对的，这不仅仅是一个循环计数器，因此一个描述性的名称会很有帮助。所以+1。

- Bill Forster

Answer 7

除了随机数生成方面的一些争议，您的洗牌算法看起来是正确的。

不过，您可以进行改进：经过一些思考，您会发现可以原地洗牌。因此，您可以直接使用输出缓冲区，而不需要分配临时数组。

- comingstorm

---

确实+1。我最终得到了其他人提供的完全相同的Fisher Yates算法。 - Bill Forster

Answer 8

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

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

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

Netscape加密的早期版本被破解，因为黑客能够预测使用的“随机”数字，因为伪随机数生成器是以当前时间为种子。请参阅维基百科上的写作。

- Eric J.