一尘不染

在恒定空间中创建1..N的随机排列

algorithm

我想枚举固定空间中数字1..N的随机排列。这意味着我无法将所有数字存储在列表中。这样做的原因是N可能非常大,超过了可用内存。我仍然希望能够一次遍历数字的排列,每次访问每个数字正好一次。

我知道对某些N可以做到这一点:许多随机数生成器随机(但完全)遍历整个状态空间。一个状态大小为32位的良好随机数生成器将发出数字0 ..(2 ^
32)-1的排列。每个数字恰好一次。

我想选择N为任何数字,例如,不限于2的幂。是否有一种算法?


阅读 212

收藏
2020-07-28

共1个答案

一尘不染

最简单的方法可能是只为比您关心的范围更大的范围创建全范围PRNG,并且当它生成的数字大于您想要的数字时,将其丢弃并得到下一个。

几乎完全相同的另一种可能性是首先使用线性反馈移位寄存器(LFSR)生成数字。这有两个优点:首先,LFSR可能比大多数PRNG快一点。其次,(我相信)设计一个LFSR会更容易一些,该LFSR产生的数字接近您想要的范围,并且仍然要确保它以(伪)随机顺序在其范围内的数字之间循环,而不会重复。

无需花费大量时间在细节上,对LFSR背后的数学进行了相当全面的研究。产生一个不重复其范围内所有数字的数字,只需要选择一组与不可约多项式相对应的“抽头”即可。如果您不想自己搜索,就可以很容易地找到几乎任何合理大小的已知表(例如,快速浏览一下,维基百科文章列出了最大19位的表)。

如果有内存可用,则至少有一个不可约的多项式,其位数可能会一直存在。这转化为一个事实,在最坏的情况下,您可以创建一个生成器,该生成器的范围大约是所需范围的两倍,因此,平均而言,您将丢弃(大致)生成的所有其他数字。给定LFSR的速度,我想您可以做到这一点,并且仍然保持可接受的速度。

2020-07-28