穷举随机数发生器

Kla*_*ark 2 random algorithm

在我的一个项目中,我遇到了在给定范围内生成一组数字的需求,该数字将是:

  • 详尽无遗,这意味着它将覆盖给定范围的大部分,而无需任何重复。

  • 这将确保确定性(每次序列都相同)。这可以通过固定种子来实现。

  • 它将是随机的(我不太熟悉随机数理论,但是我猜想有一堆描述随机性的规则。从角度来看,像0,1,2..N并不是随机的)。

我正在谈论的范围可以是整数或实数范围。

例如,如果我使用标准的C#随机数生成器生成范围为[0,9]的10个数字,我将得到以下信息:

0 0 1 2 0 1 5 6 2 6  
Run Code Online (Sandbox Code Playgroud)

如您所见,给定范围的很大一部分仍然“未开发”,并且有很多重复。

当然,输入空间可能非常大,因此记住先前选择的值不是一种选择。

解决这个问题的正确方法是什么?

谢谢。

发表评论后:好的,我同意随机词不是正确的词,但是我希望您理解我正在努力实现的目标。我想探索给定的范围,该范围可能很大,因此在内存列表中不是一个选择。如果范围是(0,10),并且我想要三个数字,我想保证这些数字会有所不同,并且它们将“描述范围”(即,它们不会全部在下半部等)。

确定性部分意味着我想使用带有固定种子的标准rng之类的东西,因此我可以完全控制序列。

我希望我把事情弄清楚了。

谢谢。

Nic*_*son 5

以下是具有不同权衡的三个选项:

  1. 提前生成一个数字列表,然后使用fisher-yates shuffle对其进行洗牌。根据需要从列表中选择。O(n)总内存,每个元素O(1)时间。随机性与您用于随机播放的PRNG一样好。三种选择中最简单的一种也是。
  2. 使用线性反馈移位寄存器,它将在重复之前恰好一次生成其序列中的每个值。O(log n)总内存,每个元素O(1)时间。但是,根据当前值确定将来的值很容易,并且LFSR最容易构造为2个周期的幂(但您可以选择2的下一个最大幂,并跳过任何超出范围的值)。
  3. 使用基于分组密码安全置换。可用于2个周期的任何异能,并且有一点点欺骗性,可以用于任意周期。O(log n)总空间和每个元素O(1)时间,随机性与分组密码一样好。实施中最复杂的三个。