2

问题由此产生。问题可以表述如下：

给定两个正整数 n 和 m，其中 m <= n，有没有办法找到一组数字，它们循环并覆盖从 0 到 n 的所有可能值？

作为一个基本示例，如果我们将 3 作为一个数字，对于current0 到 3 之间的任何数字，我们可以计算下一个值：

next = (current+3) % 4

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

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

4

2 回答 2

3

我不确定您打算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.

（这是赫尔-多贝尔定理。）

请注意，a, c == 1 对于任何 m 都满足上述标准。此外，如果 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

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

于 2013-01-16T17:01:49.040 回答
3

将每个后续数字增加任何不共享公共素因数的数字(n-m+1)将覆盖序列（例如，对于序列[2-11]（10 个数字），增加 3、7 或 9 将起作用，但 2、4、5、6 和 8不会因为它们共享一个公约数（2 和/或 5）

编辑

我提出了改组的想法，因为您似乎每次都想增加相同的数字。如果您想要一个真正的“随机”序列，其中 m 在第一个元素中，只需取出 m 并将其放在开头。不过，我不确定这对您有什么帮助。

于 2013-01-16T16:15:15.577 回答