排序不同类型对象的高效算法 [英] Efficient algorithm for ordering different types of objects

问题描述

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

Given that we have a collection of videos of different types (say types A,B and C,...), we are looking for an efficient algorithm to order these objects into a playlist so that we have maximum dispersion. That is, we want to make sure that two videos from A will not be placed back to back, if that can be avoided. The playlist will be repeating (it starts over when it ends. So this aspect should also be considered).

什么是可以执行的有效算法？以上具有良好的分散性？

What would be an efficient algorithm that could perform the above with a good dispersion?

示例输入：

• 5个对象A型（A1，A2，A3，A4，A5）


• 3个B型对象（B1，B2，
  B3）

输出-非最佳

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

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

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

This is not optimal because after A4, A5 plays and then the playlist loops back and A1 plays. Now we have played 3 videos from type A back to back.

最佳输出

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

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

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

This is optimal because we have only 2 videos of same type playing back to back.

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

推荐答案

这是我的算法，适用于多种类型，不仅限于2种类型：

Here's my algorithm that works for any number of types, not just 2:

• 调用a类型（例如A，B，C等）。


• 调用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是从零开始的，像数组索引一样。

Where the {i}th_gap is zero-based, like the array indexes.

如果您可以在恒定时间内计算出{i} th_gap（可以通过使用另一个计数器来完成），则算法为线性时间，即O（size） O（size * numTypes）。

If you can work out {i}th_gap in constant time (which can be done by just using another counter), then the algorithm is linear time, i.e. O(size) O(size * numTypes).

在您的示例中，输出为 ababaaba 。

For your example, it gives output a b a b a a b a.

编辑

重新思考：只需维护每种类型的计数就不需要那么复杂。

Re-think: it doesn't need to be so complicated if you just maintain counts of each type.

工作的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）解决方案具有更好的复杂性。

But as @Jim says, it's O(n * k), where n is totalNumItems and k is numItems.length. So his O(n log k) solution has better complexity.

编辑2

为了更好地打破平局而调整，因此更常使用物品。先前[10,1,1]的代码输出是 caaabaaaaaaa ，现在是 abaaaaacaaaa 。

Tweak to break ties better, so more frequent items are preferred. Previous code output for [10,1,1] was caaabaaaaaaa, now is 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>");

这篇关于排序不同类型对象的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！