寻找一种算法以(伪)随机顺序吐出一系列数字

Question

假设我有一系列数字:{n,n + 1,n + 2,... n + m}

如果不提前存储数字,我想创建一个函数f(),给定序列{1,2,3,... m}将以随机(或至少伪随机)顺序吐出原始集合.

例如假设我的序列是{10,11,12,13,14,15,16,17}

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

在过去的某个时刻,一位同事向我展示了一种能够做到这一点的数学算法,但是我已经忘记了除了存在之外几乎所有关于它的事情.我记得你必须事先得到序列,并从函数中使用的序列中生成一些常量.对于那些想知道的人,我遗憾地失去了与那位同事的联系.

这个问题的答案看起来很接近我想要的,但我不确定答案是否允许我提前将输出约束到特定序列.

---

编辑:

为了澄清一点,我不想存储原始序列或混洗序列.我想从原始序列生成函数f().

令人沮丧的是,我已经看到了这一点,我只是记不起来,谷歌再次找到它.

Fisher-Yates算法非常适合置换或改组卡座,但它不是我想要的.

Answer 1

有一个简单的函数可以生成[0..m-1]给定的排列m.只需选择一个数字k,相对素数m和让f(i)=(k*i) mod m.这总是产生一个排列(没有重复0<=i<m).如果k大于,则效果更好m.

例如,m = 20,设k = 137(Python代码,%表示模数):

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

这是一个非常简单的PRNG,不保证其统计特性.