排序不同类型对象的高效算法

Question

鉴于我们收集了不同类型的视频（例如A，B和C，...），我们正在寻找一种有效的算法来将这些对象排序到播放列表中，以使分散度最大化。也就是说，我们希望确保避免将A的两个视频背对背放置。播放列表将重复播放（播放结束时将重新开始。因此也应考虑此方面）。

什么是可以很好地执行上述操作的高效算法？

输入示例：

• 5个类型A的对象（A1，A2，A3，A4，A5）
• 3个类型B的对象（B1，B2，B3）

输出-非最佳

A1，B1，A2，B2，A3，B3，A4，A5

这不是最佳选择，因为在A4之后播放A5，然后播放列表循环返回，而A1播放。现在，我们已经播放了3种类型A的视频。

最佳输出

A1，B1，A2，A3，B2，A4，B4，A5

这是最佳选择，因为我们只能连续播放2个相同类型的视频。

请注意，该算法应适用于不同数量的类型和视频。

Answer 1

这是我的算法，适用于任意数量的类型，而不仅仅是 2 种：

• 将类型（例如 A、B、C...）称为 T。
• 调用 TN(T) 类型的项目数。

伪代码算法：

var size = 0;
for_each (T)
  size += N(T);

var output = array(size); // Initialised to null, to mean gap (no item)
var gapsRemaining = size;

for_each (T)
{
  var itemsRemaining = N(T);
  var i = 0;
  var limit = itemsRemaining / gapsRemaining;
  while (itemsRemaining > 0)
  {
    if (itemsRemaining / (gapsRemaining - i) >= limit)
    { output[{i}th_gap] = next_item_of_type(T)
      gapsRemaining--;
      itemsRemaining--;
    }
    else
      i++;
  }
}

其中 {i}th_gap 是从零开始的，就像数组索引一样。

如果您可以在恒定时间内算出 {i}th_gap （这可以通过使用另一个计数器来完成），那么该算法是线性时间，即O(size)O(大小 * numTypes)。

对于您的示例，它给出了输出a b a b a a b a。

编辑

重新思考：如果您只维护每种类型的计数，则不需要那么复杂。

工作 JS 代码（http://js.do/code/96801）

var numItems = [5,3]; // for AAAAABBB
var numItems = [6,3,5]; // for AAAAAABBBCCCCC
var totalNumItems = 0;
for (i=0; i<numItems.length; i++)
    totalNumItems += numItems[i];
var limits = [];
for (i=0; i<numItems.length; i++)
    limits[i] = numItems[i] / totalNumItems;
var numGaps = totalNumItems;
var output = [];
for (i=0; i<totalNumItems; i++)
{   var bestValue = 0;
    var bestType;
    for (j=0; j<numItems.length; j++)
    {   var value = numItems[j] / numGaps - limits[j];
        if (value >= bestValue)
        {   bestValue = value;
            bestType = j;
    }   }
    output[i] = bestType;
    numItems[bestType]--;
    numGaps--;
}
for (i=0; i<totalNumItems; i++)
    document.writeln(output[i]);
document.writeln("<br>");

但正如 @Jim 所说，它是 O(n * k)，其中 n 是totalNumItems， k 是numItems.length。所以他的 O(n log k) 解具有更好的复杂度。

编辑2

进行调整以更好地打破联系，因此首选更频繁的项目。[10,1,1] 之前的代码输出是caaabaaaaaaa，现在是abaaaaacaaaa。

http://js.do/code/96848

var numItems = [10,1,1];
var totalNumItems = 0;
for (i=0; i<numItems.length; i++)
    totalNumItems += numItems[i];
var limits = [];
for (i=0; i<numItems.length; i++)
    limits[i] = numItems[i] / totalNumItems;
var numGaps = totalNumItems;
var output = [];
for (i=0; i<totalNumItems; i++)
{   var bestValue = 0;
    var bestNumItems = 0;
    var bestType;
    for (j=0; j<numItems.length; j++)
    {   var value = numItems[j] / numGaps - limits[j];
        if (value >= bestValue && numItems[j] > bestNumItems)
        {   bestValue = value;
            bestNumItems = numItems[j];
            bestType = j;
    }   }
    output[i] = bestType;
    numItems[bestType]--;
    numGaps--;
}
for (i=0; i<totalNumItems; i++)
    document.writeln(output[i]);
document.writeln("<br>");