algorithm - 生成相差 1 位且无重复的随机整数序列

Question

我需要生成一个由 N 位整数组成的(伪)随机序列，其中连续的整数与前一个整数仅相差 1 位，并且该序列从不重复。我知道格雷码会生成只有 1 位差异的非重复序列，而 LFSR 会生成非重复的类随机序列，但我不确定如何结合这些想法来产生我想要的结果。

实际上，N 会非常大，比如 1000。我想随机抽取这个 2^1000 整数的大空间，但我需要生成类似于随机游走的东西，因为应用程序只能从一个数字跳到下一个翻转一位。

Answer 1

使用任何随机数生成器算法生成 1 到 N(或 0 到 N-1，具体取决于语言)之间的整数。使用结果确定要翻转的位的索引。

为了满足随机性，您需要存储以前生成的数字(感谢 ShreevatsaR)。此外，您可能会遇到不可能出现非重复答案的情况，因此这也需要回溯算法。