algorithm - 您如何以不可预测的顺序遍历整数范围？

Question

如何以难以预测的顺序遍历固定范围的整数(比如 100000-999999)？

• 假设范围可能足够大，以至于将每个可能的整数存储在一个数组中或保留一个包含您目前找到的每个元素的数组是不切实际的。
• 您必须击中范围内的每个数字一次且仅一次，并且能够知道您何时完成，即没有数字剩余

即我想要一些更优雅的东西，而不仅仅是 A) 选择一个随机数，然后 B) 检查它是否已经被使用，如果是，则返回步骤 A，原因如下(除非你能说服我否则):

• 当你开始用完数字时，那真的很糟糕
• 告诉您是否用完未使用的号码可能会非常昂贵
• 如果您有很多客户端或线程试图同时在同一范围内执行此操作，那么这种方法也可能会出现并发问题

Answer 1

线性同余随机数生成器(在 Knuth 的第 2 卷中详细介绍)将以一种不容易预测的方式逐步遍历给定范围内的每个值而不重复。基本语句是

v = k * v + l mod m

其中 m 是集合的大小，k 和 l 与 m 互质(我相信这足以保证它按预期工作)，v 是使用的值。以或多或少随机的方式选择初始值，然后从那里开始。

一个优点是它的编写速度相当快，前提是您可以避免溢出(通过限制 k 和 m，或使用任意精度的算术例程)。