我有一个洗牌问题。有很多页面和讨论关于如何完全打乱数组值，就像一副卡牌。
我需要的是一种能够均匀地将数组元素最多移动N个位置的洗牌方法。
也就是说，如果N为2，则元素I最多会被洗牌到从I-2到I+2的位置（在数组边界内）。
这被证明是棘手的，因为一些简单的解决方案会导致元素移动的方向偏向某个方向，或者移动的量不均匀。
2个回答
2
你说得对，这很棘手！首先，我们需要建立一些更多的规则，以确保我们不会创造人为的非随机结果：
- 元素可以保持在它们开始的位置。这是任何公平洗牌的必要部分，并且还确保我们的洗牌对于N=0也有效。
- 当N大于元素到数组开头或结尾的距离时，允许将其移动到另一侧。我们可以调整算法以禁止此操作，但这将违反“均匀”的要求 - 靠近任一端的元素比靠近中间的元素更有可能保持不变。
现在我们可以实际解决问题。
- 生成一个随机值数组，范围为
i + [-N, N]，其中i是数组中的当前索引。规范化超出数组范围的值（例如，-1应变为length-1，而length应变为0）。 - 在数组中查找重复值对（碰撞），并重新计算它们。您有几个选项：
- 重新计算两个值，直到它们不再相互碰撞，它们仍然可能与其他值碰撞。
- 仅重新计算一个值，直到它不再与另一个值碰撞，第一个值仍然可能会碰撞，但第二个应该是唯一的，这可能意味着更少的RNG调用。
- 识别每个冲突的可用索引集（例如，在
[3, 1, 1, 0]中，索引2可用），从该集合中选择一个随机值，并将其中一个数组值设置为所选结果。这避免了需要循环直到解决冲突，但代码更复杂，并且可能会遇到集合为空的情况。
- 无论您如何解决单个冲突，都要重复该过程，直到数组中的每个值都是唯一的。
- 现在将原始数组中的每个元素移动到生成的数组中指定的索引。
我不确定如何最好地实现＃2，建议你对其进行基准测试。如果您不想花时间进行基准测试，则可以选择第一个选项。其他优化可能会更快，但实际上可能会更慢。
理论上，此解决方案的运行时间未受限制，但在实践中应该很快终止。在使用它之前，请进行基准测试和测试。
- dimo414
2
总之：创建一个随机索引的单独数组，范围在当前索引的+/- N范围内。然后查找解决重复索引。如果从那个位置开始，解决过程可能会很困难，甚至不可能。 - anthony
第三个选项（计算可用索引集合）在有限时间内运行，但我并不确定它在一般情况下是否比无界选项更好。就像我说的，您需要进行基准测试。如果解决方案不可能，那么您的问题可能没有普遍解决方案。 - dimo414
0
我想到了一个可能的解决方案，但它有多么“天真”，我不确定。特别是在边缘，尤其是远端。
创建一个长度为N的布尔类型标志数组（表示已经交换过的元素）
对于每个索引，检查它是否已经被交换过（根据标志数组中的第一个元素），如果是，则继续下一个（见下文）
旋转标志数组，删除第一个元素（表示这个元素），并在末尾添加一个新的“未交换”元素。附注：可以使用模数数组查找来完成此操作，以避免实际移动数组内容，特别是对于大的N。
循环...
- 从0到N（或小于N，如果N加上当前索引大于要洗牌的数组）中选择一个数字。
- 如果是0，则元素与自身交换，继续下一个。
- 否则，如果该元素标记为已交换，则循环并重试。请注意，始终有两个元素可以选择，它本身和最后一个元素（除非接近要洗牌的数组的末尾）。
将当前元素与选择的未交换元素交换，将选择的元素标记为已交换在标志数组中。循环到下一个元素。
- anthony
2
我会尝试重新表述一下，以便我能够理解。您建议逐个循环遍历每个元素，确定一个有效的位置来放置它，如果该位置已经被填充，则再次尝试。是这样吗？如果我没有错的话，这将不是均匀的，因为列表末尾的元素可用位置比头部的元素少。 - dimo414
只有当它们尚未被交换时才能执行。最终，标记未被洗牌的元素的数组将变得更小。嗯，如果你考虑到N的值等于或大于数组的大小，它会退化为一个Fisher-Yates shuffle，但是如果它们以前已经被洗过，就没有再次被洗的机会。对我来说，这应该是均匀的。 - anthony
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
ppmspread/spread中存在bug吗？你是否查看过这些操作的源代码？提供文档链接会很有帮助，这样我们就能确保看到的是同样的内容。 - dimo414