我想在固定空间中列举数字1..N的随机排列.这意味着我无法将所有数字存储在列表中.原因是N可能非常大,超过可用内存.我仍然希望能够一次一个地浏览这样的数字排列,只访问每个数字一次.
我知道这可以用于某些N:许多随机数生成器随机循环遍历整个状态空间,但完全是.状态大小为32位的良好随机数发生器将发出数字0 ...(2 ^ 32)-1的排列.每个数字只有一次.
我想要选择N作为任何数字,而不是限制为2的幂.有算法吗？
Jer*_*fin 11
最简单的方法可能是创建一个范围比你想要的更大范围的全范围PRNG,当它生成一个比你想要的更大的数字时,只需扔掉它就可以得到下一个.
另一种可能性相同的变化是使用线性反馈移位寄存器(LFSR)来生成数字.这有几个优点:首先,LFSR可能比大多数PRNG快一点.其次,(我相信)设计一个产生接近你想要的范围的数字的LFSR会更容易一些,并且仍然可以确保它以(伪)随机顺序循环遍历其范围内的数字,而不需要任何重复.
没有花费大量时间在细节上,LFSR背后的数学已经被彻底研究过了.生成一个贯穿其范围内所有数字而不重复的数据只需要选择一组对应于不可约多项式的"抽头".如果你不想自己搜索它,很容易找到几乎任何合理大小的已知表格(例如,快速查看,维基百科文章列出它们的大小最多为19位).
如果存储器服务,则至少存在一个可能的位大小的不可简化的多项式.这意味着在最坏的情况下,您可以创建一个大约是您所需范围的两倍的生成器,因此平均而言,您(大致)丢弃您生成的每个其他数字.考虑到LFSR的速度,我猜你可以做到这一点并且仍然保持完全可接受的速度.
Dan*_*her 10
一种方法是
p大于的素数N,最好不要大得多.g模的原始根p,即一个数1 < g < p,使得g^k ? 1 (mod p)if和only if k是其倍数p-1.g^k (mod p)了k = 1, 2, ...,而忽略了比更大的价值N.对于每一个素数p,都有?(p-1)统一的原始根,所以它有效.但是,找一个可能需要一段时间.一般来说,找到合适的素数要容易得多.
为了找到原始根,我对试验和错误没有什么明显的了解,但是可以通过p适当地选择素数来增加快速查找的概率.
由于原始根的数量是?(p-1),如果r在1到1的范围内随机选择,p-1直到找到原始根的预期尝试次数是(p-1)/?(p-1),因此应该选择p使得?(p-1)相对较大,这意味着p-1必须具有很少的不同素数除数(除了因子2之外,最好只有大的除数).
除了随机选择之外,还可以按顺序尝试是否2, 3, 5, 6, 7, 10, ...是原始根,当然跳过完美的权力(或者不是,它们通常被快速消除),这不应该大大影响所需的尝试次数.
因此,它归结为检查数字x是否是原始根模数p.如果p-1 = q^a * r^b * s^c * ...使用不同的素数q, r, s, ...,x则是原始根,当且仅当
x^((p-1)/q) % p != 1
x^((p-1)/r) % p != 1
x^((p-1)/s) % p != 1
...
因此,需要一个体面的模幂运算(通过重复平方取幂,适合于此,通过每个步骤的模数减少).并且找到素因子分解的好方法p-1.然而,请注意,即使天真的试验除法仅为O(√p),而置换的生成也是Θ(p),因此因子分解是最优的并不是最重要的.