生成不重复的随机序列

Question

我在这里读到了一些有关生成无重复随机序列的帖子（例如Create Random Number Sequence with No Repeats），并决定为自己的需要实现它。

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

至少有几种可能的操作，如交换两个位，反转一个位，循环移位。如果我们只使用上述操作，序列的质量不会很好，因为相邻的计数器将产生具有相似数量的零和一的结果。真正的改变游戏规则的是将一个位与另一个位异或。现在序列看起来好多了，但问题是：

• 是否存在足够的操作的最小子集（例如反转位+通过另一个位异或位），添加任何其他操作只会使算法更难读而没有额外的好处
• 如何大致猜测给定范围的操作数，以使序列足够好。例如，对于从0到31的数字，200个操作会产生视觉上良好的结果，但对于范围为0..199的200个操作，有时会产生接近数字的块。
• 是否有用于测试此类序列的算法或测试套件。我知道并曾经使用过可以测试一般随机序列的测试套件，但这是一个不同的问题，因此可能需要一些特殊的测试套件，或者至少需要将其转换回一般的随机世界

更新：正如我在这里的评论中发布的那样，已经有了这样的生成器：AES加密，但不幸的是它只能用于128位范围。

谢谢

Max

- Maksee

Answer 1

问题：

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

解决方案：

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

在Matlab中：

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

% iz是您的列表。

- BarryV

---

这是纯粹的天才。 - Ron Jensen

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函数连接在一起。 有两件事情值得注意： - 保持计数器i的序列从0到N-1。

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

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

• 找到一个相对质于n的随机数r1和另一个介于0和n-1之间的随机数r2。您的第i个数字= r2^r % n。

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

有一件事情值得注意的是，如果你的范围是0..N-1，只需找到一个与N互质的大数P，并选择另一个随机数。

- user485440

---

也许这不是最好的算法 [需要引用 ;P]，但你应该寻找一些类似于洗牌卡组的东西。 - Fabio Filippi

你能定义一下“不是最佳的”吗？我认为这个解决方案具有选择任意排列并具有均匀概率的特性。可能存在更快的解决方案或者使用更少的随机位的解决方案，但我表示怀疑。 - user485440

谢谢，但实际上我想要实现的是可以用于任何范围的东西，即使可能需要使用数组方法来占用更多的空间。实际上，AES加密是这样一个生成器，它将唯一的输入与不重复的输出链接起来，但仅限于128位范围，我只是想要一些类似的算法，但适用于任何位范围。 - Maksee