algorithm - 随机播放列表（带有重复项）以避免相同的元素彼此相邻

Question

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

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

Answer 1

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

Answer 2

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

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

对于较小的集合，没有什么是可能的，这取决于欺骗的数量。所以对于一个非常小的集合的解决方案只会是好的基本随机化（我们回到第一句话）。

Answer 3

就我个人而言，我认为最简单的处理方法是将数组随机化，然后对其进行迭代，直到找到 2 个具有相同值且彼此相邻的元素。当您在彼此旁边找到 2 个相同的值时，通过遍历数组将后者移动到数组中的另一个位置，直到找到一个位置，使其不在另一个相同值旁边。如果找不到值，只需将其保留在原处，然后继续处理数组的下一个元素。这可能不是最优化的解决方案，但适用于较小的数据集，并且可能是最容易编程的。

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 向后检查是值得的，如果有任何重复的拖尾，请尝试早点将它们放入混合中。