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

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

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

这question's答案看起来接近我想要的，但我不确定答案是否允许我提前将输出限制为特定序列。

---

编辑:

再澄清一点，我不想存储原始序列或打乱后的序列。我想从原始序列生成函数 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，不保证其统计属性。