快速生成随机混乱

Question

我希望随机均匀地产生混乱。换句话说：对向量进行打乱，使得没有元素留在其原始位置。

要求：

• 均匀采样（每个乱序以相等的概率生成）
• 实际的实现比拒绝方法更快（即不断生成随机排列，直到我们发现混乱）

到目前为止，我找到的答案都不是令人满意的，因为它们要么没有均匀采样（或未能证明均匀性），要么没有与拒绝方法进行实际比较。排列1/e = 37%是紊乱，它提供了一个线索，说明相对于拒绝方法，人们最多可以期望什么性能。

我发现的唯一进行实际比较的参考文献是在这篇论文中，该论文对他们提出的算法进行了 7.76 秒的基准测试，而对拒绝方法进行了 8.25 秒的基准测试（参见第 73 页）。这仅加速了 1.06 倍。我想知道是否有可能有更好的东西（> 1.5）。

我可以实现和验证论文中提出的各种算法，并对它们进行基准测试。正确地做到这一点将需要相当多的时间。希望有人做过，能给我一个参考。

Answer 1

这只是一个想法，但我认为它可以产生均匀分布的混乱。但是您需要一个最多包含 N/2 个元素的辅助缓冲区，其中 N 是要排列的项目的大小。

• 首先是为 value 选择一个随机（1，N）位置1。
  • 注意：为了简单1 to N起见而不是0 to N-1。
• 那么对于 value ，如果落在位置上2，位置将为随机（1，N-1），否则为随机（1，N-2）。12
• 该算法将遍历列表并仅计算尚未使用的位置，直到到达 value 所选的随机位置2，当然该位置2将被跳过。
• 对于值，3算法将检查位置是否3已被使用。如果使用的话，pos3 = random(1,N-2)如果没有的话，pos3 = random(1,N-3)
• 同样，算法将遍历列表并仅计算尚未使用的位置，直到达到 count= pos3。然后将值放在3那里。
• 这将适用于下一个值，直到将所有值完全放置到位。

这将产生统一的概率混乱。

优化将集中在算法如何pos#快速达到目标。该算法可以使用类似堆的方式来搜索尚未使用的位置，而不是遍历列表来计算尚未使用的位置，而不是一一计数和检查位置。或者除了类似堆搜索之外的任何其他方法。这是一个需要解决的单独问题：how to reached an unused item given it's position-count in a list of unused-items.