O(1)内存中的随机序列迭代？

Question

假设您想以随机顺序迭代序列[0到n],只访问每个元素一次.有没有办法在O(1)内存中执行此操作,即不创建[1..n]序列std::iota并运行它std::random_shuffle？

某种迭代器以随机顺序吐出序列将是最佳的.

要求是应该可以通过选择另一个种子来获得另一个随机顺序.

Answer 1

如果你可以就地改变序列,你可以简单地从0-N重复绘制一个随机数,然后擦除你访问过的元素,或者将它交换到最后,或者这样的方案.

Answer 2

从理论上讲,如果你构建了一个周期正好为n的随机数生成器,并覆盖了0..n中的所有值,那么运行这一次就可以得到你喜欢的内容.

当然,这可能不是一般解决方案,至少如果你正在寻找动态的东西,因为你必须预先创建PRNG以及你如何做到这一点取决于n.

此外,PRNG本身需要具有"O(1)"内部状态 - 有一些非常明显的方法可以构建违反该规则的PRNG ;-) (3认同)
您可以为n的许多值创建一个全周期线性同余RNG,并且已知这些值具有O(1)内部状态.鉴于n的值,我不知道计算这种生成器的任何通用方法.我所知道的是,对于n的某些值,可以构建O(1)存储器PRNG __并且还可以生成n个多个序列的一些值.我不知道如何动态构造这些任意n(或者即使存在一般算法也是如此 - 在LCRNG的情况下,IFF限制了什么给你一个完整的周期). (2认同)