如何逐个生成一大组打乱后的唯一数字？

Question

假设我想生成一个包含 1000 个唯一数字的随机列表（数字可以是 1 到 1000 的范围）。我可以通过将范围从 1 到 1000 扩展到实际列表，然后随机打乱元素来做到这一点。语言并不重要，但在 python 中它可能是这样实现的：random.shuffle(list(range(1000)))。

但是，如果我需要生成 100 亿个数字怎么办？将范围扩展到列表将需要大量内存（如果以 8 字节存储数字，则大约需要 74 GB 内存）。洗牌还需要大量的内存和时间。但并不需要一次生成所有的数字，而是最好一个一个地生成，保存状态，而不是存储所有数字而填满内存，而只存储一个。

数字仍然需要唯一。有没有用于此目的的算法？

如果有一种方法可以在给定的生成步骤中快速恢复生成器的“状态”，那就太好了。例如，如果我已经生成了 100 万个数字，而下一个数字必须是 10，那么如果我能够有效地（无需再次重新生成该百万个数字）以 100 万为步长恢复状态并生成下一个数字，那就太好了 - 10.

有这样的算法吗？

Answer 1

有这样的算法吗？

是的。您可以使用可逆哈希函数精确地获得所需的内容。

假设您想要生成0和之间的随机非重复数字n：您需要一个位种子可逆哈希函数m=log2(next_power_of_two(n))，并简单地迭代从 0 开始的所有数字以对n这些数字进行哈希处理并拒绝每个大于 n 的数字。

这是一篇关于它的精彩文章：https ://andrew-helmer.github.io/permute/

有一个小警告：范围必须足够大，以便能够为其编写良好的哈希函数。

如果有一种方法可以在给定的生成步骤中快速恢复生成器的“状态”，那就太好了。

只需存储最后一次迭代索引和种子即可实现这一点。