c++ - 创建无重复的随机数序列

Question

复制:

Unique random numbers in O(1)?

我想要一个伪随机数生成器，它可以以随机顺序生成不重复的数字。

例如:

随机(10)

可能会回来 5、9、1、4、2、8、3、7、6、10

除了确定数字范围并将它们随机排列或检查生成的列表是否有重复之外，还有更好的方法吗？

---

编辑:

我还希望它能够有效地生成没有整个范围的大数字。

---

编辑:

我看到每个人都在建议洗牌算法。但是，如果我想生成大的随机数(1024 字节+)，那么该方法会比我只使用常规 RNG 并插入到 Set 中直到达到指定长度需要更多的内存，对吧？有没有更好的数学算法。

Answer 1

您可能对线性反馈移位寄存器感兴趣。 我们曾经用硬件构建这些，但我也用软件完成了它们。它使用一个移位寄存器，其中一些位异或并反馈到输入，如果您选择正确的“抽头”，您可以获得与寄存器大小一样长的序列。也就是说，一个 16 位的 lfsr 可以产生一个 65535 长且没有重复的序列。它在统计上是随机的，但当然是可重复的。此外，如果做错了，你可能会得到一些令人尴尬的短序列。如果您查找 lfsr，您会发现如何正确构造它们的示例(即“最大长度”)。