algorithm - 生成从 0 到 n 的整数的无状态伪随机排列？

Question

问题产生于 this one .该问题可以表述如下:

Given two positive integers n and m, with m <= n, is there a way to find a suite of numbers, which cycles and covers all possible values from 0 to n?

作为一个基本示例，如果我们将 3 作为一个数字，对于任何介于 0 和 3 之间的 current 数字，我们都可以计算下一个值:

next = (current+3) % 4

这将循环。例如:1 -> 0 -> 3 -> 2 -> 1 等。我“偶然”找到了这个解决方案，它甚至是通用的 ((i + n) % (n + 1)对于任何 n)，我无法从数学上证明它。而且有点太明显了。

有没有更好的方法来生成这样的排列？

Answer 1

我不确定您打算在问题中引用什么m，或者您如何定义“一组数字”)。但是，获得数字循环的一种方法是使用以下形式的递归(或迭代):

next = f(current)

对于某些函数 f。例如，线性同余 RNG 使用迭代:

x = ( a · x + c ) mod m   where 0 < a, c < m

它们并不总是产生从 0 到 m-1 的所有值，但在某些情况下它们会产生:

c and m are relatively prime

a - 1 is divisible by every prime factor of m (not including m)

if m is divisible by 4, a - 1 is divisible by 4.

(这是赫尔-多贝尔定理。)

请注意，对于任何 m，a, c == 1 都满足上述条件。此外，如果 m 是质数，则 a 和 c 的任何值都满足条件，如果 m 是 2 的幂，则任何 a，c 都满足条件，使得 a == 1 mod 4 和 c == 1 mod 2. 然而，对于某些 m 值(例如 6)，a 唯一有效的值是 1。

这可能不符合“无状态”的条件，但我认为没有任何严格的无状态解决方案；例如，您可能会寻找这样的函数 f:

f(0), f(1),... f(m-1)

是

的排列

0, 1, ..., m-1

这样您就可以通过为 i 的连续值调用 f(i) 来生成循环。但这仍然是一种状态，因为您必须记住您使用的 i 的最后一个值，