创建没有重复数字的随机数序列

Question

重复：

如何在O(1)时间内生成不重复的随机数？

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

例如：

random(10)

可能返回 5, 9, 1, 4, 2, 8, 3, 7, 6, 10 等等。

除了改变数字范围并对其进行洗牌，或者检查生成的列表是否有重复值之外，还有更好的方法吗？

---

编辑：

同时，我希望它在生成大量数字时具有高效性，而无需生成整个范围的数字。

---

编辑：

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

- Unknown

---

有一些伪随机数生成器（PRNGs）在整个周期结束之前不会重复——只要它们使用上一个生成的数字作为下一个数字的种子，就具备这个特性。 - derobert

关于您的编辑：如果您使用常规的随机数生成器并将数字添加到集合中，您认为会使用多少内存？与预先生成数字列表使用的内存相同... - David Z

在O(1)时间内生成不重复的随机数。 - Pete Kirkham

这并不是重复的问题，因为原帖作者已经表明他想从一个非常大的范围内生成一小组唯一值。在这种情况下，洗牌并不合适。 - Bill the Lizard

@Bill，那个问题的正确答案（与被接受的答案相反）不需要洗牌。 - Pete Kirkham

Answer 1

您可能对线性反馈移位寄存器感兴趣。我们过去通常使用硬件来构建它们，但我也用软件实现过。它使用一个移位寄存器，其中一些位进行异或并反馈到输入，如果您选择恰当的“触点”，则可以得到与寄存器大小相同长度的序列。也就是说，一个16位的LFSR可以生成一个长度为65535的不重复序列。它在统计学意义上是随机的，但当然是可重复的。另外，如果做错了，可能会得到一些非常短的序列。如果您查找LFSR，将找到如何正确构建它们的示例（即“最大长度”）。

- gbarry

---

你知道这个算法在随机性方面与线性同余 RNG 相比如何吗？我为这个算法投了赞成票。 - Unknown

抱歉，我不是数学专家。我看不出它们之间有任何相似之处（尽管我本能地怀疑）。 - gbarry

最好不要尝试从头开始构建随机数生成器(RNG)，因为太容易出错了。如果你已经有一个像Boost中的可用的不错的RNG，那么你应该尽可能地使用它。几乎所有周期等于模数的方法都会产生那么多不重复的数字，但对你来说似乎毫无用处。 - Joey

LFSR是一种非常有效且简单的解决方案，但您必须为其选择合适的常数以使其正常工作。互联网上有相关资源可协助进行选择。 - Steve Melnikoff

Answer 2

洗牌是一个非常有效的方法，可以用来打乱数据集（前提是你不使用朴素算法引入偏差）。请参见Fisher-Yates shuffle。

- Mitch Wheat

---

请给这个旧回答点踩的人留下评论。谢谢。 - Mitch Wheat

OP特别要求一种不需要存储整个范围并对其进行洗牌的方法。 - Pablo Halpern

请仔细查看：这些额外的要求是后来添加的。 - Mitch Wheat

Answer 3

如果一个随机数保证不重复，那么它就不再是随机的，随着数字的生成，“随机性”会逐渐减少（在生成九个数字后，random(10) 的预测性变得相当高，在仅生成八个数字后，您就有50-50的机会）。

- Motti

---

他使用“随机”一词的含义并不像你那样严格。想象一下，他的应用程序是逐个填充网格中的单元格，直到每个单元格都被填满，从而产生一个漂亮的视觉效果。某些单元格序列将产生规律的视觉图案。“随机”序列在他所指的意义上则不会产生。 - Jonathan Hartley

Answer 4

我理解您不想为大范围的随机数进行洗牌，因为您需要存储整个列表才能这样做。

相反，使用可逆伪随机哈希。然后依次输入值0 1 2 3 4 5 6等。

有无限数量的这样的哈希。如果将它们限制为2的幂，则生成它们并不太困难，但可以使用任何基数。

例如，如果您想浏览所有2^32个32位值，则可以使用以下哈希。在这种情况下，整数运算的隐式模2^32对您有利，因此这是最容易编写的方法。

unsigned int reversableHash(unsigned int x)
{
   x*=0xDEADBEEF;
   x=x^(x>>17);
   x*=0x01234567;
   x+=0x88776655;
   x=x^(x>>4);
   x=x^(x>>9);
   x*=0x91827363;
   x=x^(x>>7);
   x=x^(x>>11);
   x=x^(x>>20);
   x*=0x77773333;
   return x;
}

- Arno Setagaya

---

在这个上下文中，“reversable”是什么意思？ - Daniel Earwicker

我不知道，我原本期望的是“n == f(f(n))”，但显然不是这种情况。 - Vatine

可逆在此指没有信息丢失。如果您有 y=f(x)，则存在反函数 x=g(y)。这保证了您具有一对一映射，因此您的伪随机序列不会重复。 - SPWorley

Answer 5

洗牌是在特定范围内生成无重复随机数的最佳方法。你描述的方法（随机生成数字并将它们放入集合中，直到达到指定长度）效率较低的原因是因为会产生重复数字。理论上，该算法可能永远无法完成。最好的情况下，它将以不可预知的时间完成，而洗牌则始终以高度可预测的时间运行。

对编辑和评论的回应：

如果像你在评论中所示，数字范围非常大，并且你想要随机选择相对较少的数字而又不重复，那么重复的可能性会迅速减小。范围与选择数量之间的差距越大，重复选择的可能性就越小，而你在问题中描述的选择和检查算法的性能就越好。

- Bill the Lizard

---

但是，如果我想生成100个数字，这些数字的范围可以从1到2^64位，那么创建一个包含2^64个数字的列表，然后从中进行随机洗牌就没有意义了。 - Unknown

不，它不会。在这种情况下，碰撞的可能性将大大降低。如果那是你所需的样本和范围，那么你问题中的例子会非常误导。 - Bill the Lizard

Answer 6

如果你不介意随机性能够中等，而且元素数量允许的话，可以使用线性同余随机数生成器。

- starblue

---

你知道这个算法在随机性方面与LSFR相比如何吗？我为这个算法投了赞成票。我有点担心数字会落在“m1/n超平面”中。 - Unknown

LCGs存在一些严重的问题，但超平面问题存在于所有PRNG中。这取决于算法、状态字大小以及在哪些维度上选择良好的参数以及有多少个超平面。例如，Mersenne Twister在624维超平面上产生点。 - Joey

啊，我明白了，谢谢你解释所有伪随机数生成器都有这个限制。 - Unknown

Answer 7

使用GUID生成器（例如.NET中的生成器）如何呢？虽然不能保证不会出现重复，但是出现的概率非常低。

- Rashack

---

据我所知，当前时间是 GUID 生成的一部分。因此，它肯定与数字之间存在相关性。 - dmeister

Answer 8

这个问题之前已经被问过了 - 可以参考我之前回答的问题。简而言之：您可以使用块密码来生成安全（随机）置换，而不必在任何时候存储整个置换。这样可以覆盖您想要的任何范围。请参见链接：https://dev59.com/rkXRa4cB1Zd3GeqPvN23#320213。

- Arachnid

Answer 9

如果你想要创建大型（例如64位或更大）且不重复的随机数，那么就直接创建它们。如果你使用的是一个具有足够熵的好的随机数生成器，那么生成重复的概率是如此微小，以至于不值得担心。

例如，在生成加密密钥时，没有人会费心去检查他们是否已经生成了相同的密钥；因为你信任你的随机数生成器，认为专门攻击者无法获得相同的密钥，那么你为什么会期望你会意外地得到相同的密钥呢？

当然，如果你有一个糟糕的随机数生成器（例如Debian SSL随机数生成器漏洞），或者生成的数字足够小，生日悖论birthday paradox给你带来高碰撞几率，那么你需要采取一些措施确保你不会得到重复的结果。但对于使用好的生成器生成的大型随机数，只需相信概率不会给你任何重复结果。

- Brian Campbell

Answer 10

在生成数字时，使用Bloom过滤器来检测重复项。这将使用最少的内存。根本不需要存储系列中先前的数字。

权衡是您的列表可能无法穷尽您的范围。如果您的数字确实是256^1024的数量级，那几乎没有任何权衡。

（当然，如果它们实际上是在该比例上随机的，即使费心检测重复项也是浪费时间。如果地球上的每台计算机每秒生成一万亿个该大小的随机数，并持续数万亿年，碰撞的机会仍然是绝对微不足道的。）

- Imbue