algorithm - 寻找有限的洗牌算法

Question

我有一个洗牌问题。有很多关于完全洗牌值数组的页面和讨论，就像一叠卡片。

我需要的是一个 shuffle，它将数组元素从其起始位置最多 N 处均匀地移动。

即如果 N 为 2，则元素 I 最多被打乱到从 I-2 到 I+2 的位置(在数组的边界内)。

这已被证明是棘手的，一些简单的解决方案会导致元素移动的方向偏差，或不均匀的量。

Answer 1

你是对的，这很棘手!首先，我们需要建立更多的规则，以确保我们不会人为地创建非随机结果:

• 元素可以保留在它们开始的位置。这是任何公平洗牌的必要部分，也确保我们的洗牌适用于 N=0。
• 当 N 大于元素到数组开头或结尾的距离时，允许将其移动到另一侧。我们可以调整算法以禁止这样做，但它会违反“统一”要求 - 靠近两端的元素比靠近中间的元素更有可能留在原地。

现在我们可以真正解决问题了。

1. 生成一个范围为 i + [-N, N] 的随机值数组，其中 i 是数组中的当前索引。规范化数组边界外的值(例如，-1 应变为 length-1，length 应变为 0)。
2. 在数组中查找成对的重复值(冲突)，并重新计算它们。你有几个选择:
   • 重新计算这两个值，直到它们不再相互冲突，它们仍然可能与其他值发生冲突。
   • 只重新计算一个，直到它不与另一个发生冲突，第一个值仍可能发生冲突，但第二个应该现在是唯一的，这可能意味着对 RNG 的调用更少。
   • 确定每次碰撞的可用索引集(例如，在 [3, 1, 1, 0] 索引 2 中可用)，从中选择一个随机值设置，并将数组值之一设置为所选结果。这避免了在解决冲突之前需要循环，但代码更复杂，并且有遇到集合为空的情况的风险。
3. 无论您如何解决单个冲突，重复该过程，直到数组中的每个值都是唯一的。
4. 现在将原始数组中的每个元素移动到我们生成的数组中指定的索引处。

我不确定如何最好地实现 #2，我建议您对其进行基准测试。如果您不想花时间进行基准测试，我会选择第一个选项。其他优化可能更快，但实际上最终可能会更慢。

该解决方案在理论上具有无限的运行时间，但在实践中应该会很快终止。同样，在任何关键的地方使用它之前，对其进行基准测试和测试。