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

Question

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

即我想要比A更优雅的东西A)选择一个随机数然后B)检查它是否已经被使用过,如果是这样的话,回到步骤A,原因如下(除非你能说服我):

Answer 1

线性同余随机数发生器(在Knuth的第2卷中以难以理解的细节覆盖)将以不易于预测的方式逐步遍历给定范围中的每个值而不重复.基本陈述是

v = k * v + l mod m

其中m是集合的大小,k和l是m的相对素数(我相信这足以保证它按照需要工作),而v是正在使用的值.以某种或多或少的随机方式选择初始值,然后从那里开始.

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

我试过这个,发现它在重复数字之前没有用尽范围,这取决于我选择的常数值.根据维基百科条目http://tinyurl.com/2qx2xb,如果您希望序列是详尽的,还有其他限制:k-1必须可被m的所有素因子整除,并且k-1必须可被4整除m可以被4整除.因此,对于m = 100 k,可以是21,41,61或81.似乎非常有限.(甚至可能,如果m本身是素数？)文章还说l必须受到m的约束,我试图违反并发现它似乎无论如何都有效. (3认同)