3

我有一个洗牌的问题。有很多页面和讨论关于完全洗牌一系列值，比如一摞牌。

我需要的是一个随机播放，它将在远离其起始位置的最多 N 个位置均匀地置换数组元素。

也就是说，如果 N 为 2，则元素 I 最多将被洗牌到从 I-2 到 I+2 的位置（在数组的范围内）。

事实证明，使用一些简单的解决方案会导致元件运动的方向偏差或不均匀的量，这很棘手。

4

2 回答 2

2

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

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

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

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

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

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

于 2015-08-20T05:27:28.330 回答
0

尽管我不确定它有多“幼稚”，但我想出了一种可能的解决方案。尤其是在边缘，尤其是远边缘。

  1. 创建一个标志数组（布尔值）N long（表示已交换的元素）

  2. 对于在每个索引处检查它是否已经被交换（根据标志数组中的第一个元素），如果是，则继续下一个（见下文）

  3. 旋转标志数组，删除第一个元素（表示此元素），并添加一个新的“未交换”元素到结尾。旁白：这可以使用模数数组查找来完成，以避免必须实际移动数组内容，尤其是对于大 N

  4. 环形...

    • 选择一个从 0 到 N 的数字（或小于 N，如果 N 加上当前索引大于被洗牌的数组。
    • 如果为 0，元素与自身交换，移动到下一个。
    • 否则，如果该元素标记为已交换，则循环并重试。请注意，flags 数组中始终有 2 个元素可以选择，它本身和最后一个元素（除非接近被洗牌的数组末尾）

  5. 用选定的未交换元素交换当前元素，在标志数组中将选定元素标记为交换。循环到下一个元素

于 2015-08-26T00:37:37.763 回答