打乱列表（包含重复项）以避免相同的元素彼此相邻

Question

我想知道是否有一种“最佳”方法来打乱包含重复项的元素列表，以便尽可能避免 array[i] == array[i+1] 的情况。

我正在研究加权广告显示（我可以调整任何给定广告商的每次旋转的显示数量），并且希望避免同一广告商连续出现两次。

Answer 1

这与 这个非常相似问题。 如果您用广告商替换示例中的 A、B 和 C，我认为您会遇到同样的问题。 也许为此建议的一些解决方案可以帮助您。

Answer 2

基本随机化应该在大集合中引起足够的分散。

如果您想进一步减少这种情况（根据集合的不同，这甚至可能没有必要），最简单的方法是在随机化后肯定找到附近的受骗者并移动它们（但您可能会创建模式）。 更好的方法可能是创建包含并排重复的子集并重做随机化。

对于较小的集合，可能什么都不可能，具体取决于受骗者的数量。 因此，对于非常小的集合，解决方案只能是良好的基本随机化（我们回到第一句话）。

Answer 3

就我个人而言，我认为处理这个问题的最简单方法是随机化数组，然后迭代它，直到找到两个相邻的具有相同值的元素。 当您发现彼此相邻的两个相同值时，通过迭代数组将后一个移动到数组中的另一个位置，直到找到一个位置，使其不在另一个相同值旁边。 如果找不到值，请将其保留在原处，然后继续处理数组的下一个元素。 这可能不是最佳的解决方案，但对于较小的数据集来说就很好，而且可能是最简单的编程。

Answer 4

您可能拥有的最大重复数是多少？ 2、3，有吗？

Answer 5

作为参考，我的（非常）天真的方法是这样的（实际上使用 LINQ/SQL 调用，但这被简化了）：

var advertisers = getAdvertisers();
var returnList = new List();
int totalWeight = sumOfAllAdvertisersWeight();
while (totalWeight > 0)
{
    for (int i=0; i<advertisers.Count; i++)
    {
        if (advertisers[i].Weight > 0)
        {
            returnList.add(advertisers[i]);
            advertisers[i].Weight--;
            totalWeight--;
        }
    }
}
return returnList;

这将避免重复直到最后，但是是的，之后通过 returnList 向后检查以及是否有任何重复是值得的重复拖尾，尝试将它们尽早放入混合物中。