这个改组算法有什么问题吗？
我一直在做一些休闲度假计算。 我的迷你项目是对意大利“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=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的答案，因为事实certificate我正在重新发现Fisher-Yates算法，并揭示了这个问题的核心。 当然，通过预先做一些研究，我可以节省自己的时间和精力也就不足为奇了。 但另一方面，这是一个有趣的爱好项目。 模拟的其余部分是常规的，这是最有趣的部分，而且我会因为没有自己去做而剥夺了自己的享受。 此外，我试图模拟一个男人从一个袋子里拿出弹珠，而且在这件作品中已经很晚了，我意识到这种情况与洗牌很相似。
另一个值得注意的是，肯有一个小缺陷，他指出经常重复模式rand（）％N并不是从0..N-1范围内挑选随机数的好方法。
最后，我的Fisher-Yates版本缺乏优雅的技巧，可以实现适当的混乱。 结果，我的算法最终会得到一个同样随机但反向的混乱。
您正在使用Fisher-Yates混洗算法 。
使用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; } }
看起来您的代码可能有效，但我不确定。 它比标准算法更混淆。
int idx = x%i; // eg i=90 idx is random in range 0..89
它在该范围内，但它不是均匀分布的，除非90（或NBR）除以max（rand（））。 如果您使用的是2位计算机，那可能并非如此。 例如，idx稍微更可能是0而不是89。
分析算法以检查它们是否真正是随机的非常困难。
除了拥有大学数学水平的人（或美国人所说的数学专业），这甚至超出了大多数人的技能甚至validation。
因此，您应该尝试使用已构建的算法。
你看过std :: random_shuffle（）吗？
void bag( int random_sequence[NBR] ) { for(int i=0; i
从std :: random_shuffle（）页面引用：
该算法在Knuth的第3.4.2节（DE Knuth，The Art of Computer Programming，Volume 2：Seminumerical Algorithms，第二版，Addison-Wesley，1981）中描述。 Knuth称赞Moses和Oakford（1963）和Durstenfeld（1964）。 注意有N！ 排列N个元素序列的方法。 Random_shuffle产生均匀分布的结果; 也就是说，任何特定排序的概率是1 / N！。 这个评论很重要的原因是有许多算法似乎乍一看实现序列的随机改组，但实际上并没有在N上产生均匀分布！ 可能的排序。 也就是说， 很容易让随机洗牌错误 。
rand() % i的替代方案将具有更好的近均匀分布（以性能为代价）是(int) ((rand() / (double) (RAND_MAX+1)) * i) 。
或者，使用已知效果良好的伪随机数生成算法，例如Mersenne twister 。
只是几个风格点：
- 获取具有给定长度的数组的签名可能会产生错觉，即编译器保证参数至少包含IDX元素。 不是。
- 我可能会给第二个for循环中的循环索引一个像marblesRemaining这样更具说服力的名称，所以它更清楚它是什么，不需要通过注释来解释。 它还将它与第一个循环中完全不同的用途分开。
除了随机数生成，你的随机数算法看起来是正确的。
但是你可以改进它：通过一点点思考，你可以看到你可以将数字改组到位。 因此，您可以只使用输出缓冲区，而不是分配临时数组。
正如其他人已经评论过的那样，使用经过validation的改组算法。
值得注意的是，您的C / C ++库仅提供伪随机数。
需要高可靠性的随机化算法的系统使用专用硬件来生成随机数。 高端扑克网站就是一个很好的例子。 例如，参见Pokerstars的随机数生成技术。
Netscape加密的早期版本被打破，因为黑客能够预测所使用的“随机”数字，因为伪随机数生成器以当前时间播种。 在维基百科上看到这篇文章 。