生成没有重复的随机序列

Question

我在这里读了几篇关于生成不重复的随机序列的文章（例如 创建随机序列没有重复的数字序列）并决定根据自己的需要实现它

实际上这是一种算法，对当前计数器的位应用一些非破坏性（可逆）操作以获得伪随机数应该只出现一次。由于操作是可逆的，不同的源编号将给出不同的结果编号。

至少有几种可能的操作，例如交换两位、反转一位、循环移位。如果我们只使用提到的那些，序列的质量不会很好，因为附近的计数器将产生具有相似数量的 0 和 1 的结果。真正的游戏规则改变者是一点一点的异或。现在序列看起来好多了，但问题是：

• 是否有足够的最小操作子集（例如反转位+异或位另一个位）并添加任何其他只会使算法更难以阅读，同时不给出额外的好处
• 我怎样才能大致猜测给定范围内的操作数量以使序列足够好。例如，对 0 到 31 之间的数字进行 200 次运算可以提供视觉上良好的结果，但对 0..199 范围进行 200 次运算有时会得到接近数字的块。
• 是否有用于测试此类序列的算法或测试套件。我知道并使用过一次可以测试一般随机序列的套件，但这个是不同的，所以可能需要一些特殊的套件，或者至少需要一些转换回一般随机世界

更新：正如我在此处的评论中发布的那样，有已经有一个像这样的生成器：AES Encryption，但不幸的是它只能用于 128 位范围。

谢谢马克斯

​

Answer 1

问题：

生成 1 到 N 之间的唯一随机整数列表。

解决方案：

1. 生成 N 个随机数；高斯或均匀......
2. 对它们进行排序；保存索引（即列表中每个值的位置）
3. 排序的索引就是您的列表。

在 Matlab 中：

z = rand( [N 1] );
[dummy iz] = sort(z);

% iz 是您的列表。

Answer 2

除非您有充分的理由，否则您不想重新发明伪随机生成。很可能会出错。我建议从 A[i]=i 的数组开始，

然后执行以下操作：

for (i=0; i< n; i++) {
  j = random_number_between(i,n-1);
  swap(A[i],A[j]);
}

编辑
这是对以下评论的回应：

您希望序列有多随机。请注意，随机选择的排列中的固有信息是 log(n!)，它接近 n/e 位。所以你确实需要生成那么多随机位。现在，由于您希望将这些随机位存储在任何地方，我认为（更像是直觉而不是数学证明），如果没有那么多存储，就很难进行真正的随机排列）。

但如果您只想要一个不容易进行逆向工程的序列，您可以将多个 1:1 函数一个接一个地连接起来。
我想到两件事：
- 为从 0 到 N-1 的序列保留一个计数器 i。

• 在 i 上执行 log_2(N/2) 位翻转，其中要翻转的位是在启动序列时随机选择的。

• 使用上述方法在序列开头生成 log_2(N) 位的随机排列，然后交换上面结果中的位。

• 找到一个与 n at 互质的随机数 r1 和另一个介于 0 和 n-1 之间的随机数 r2。你的第 i 个数是 = r2^r % n。

这些的某种组合应该会给你一个难以逆向工程的序列。关键是注入的​​随机位越多，逆向工程就越困难。

我想到的一件事是，如果你的范围是 0..N-1，只需找到一个与 N 互质的大数 P，然后选择另一个随机数