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

一尘不染

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

algorithm

鉴于我们收集了不同类型的视频（例如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个相同类型的视频。

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

阅读 249

2020-07-28

共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（大小）~~ O（大小*
numTypes）。

对于您的示例，它给出output 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>");

2020-07-28