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

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

这个结果是最优的，因为我们只有两个相同类型的视频连续播放。

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

- Yohan Liyanage

---

你的意思是这个列表会无限循环，而我们想要尽可能减少连续播放同一组视频的数量吗？ - Codor

我理解的是否正确，您只想最小化连续项目中最大的数量：即，如果无法避免，您更喜欢多次连续出现三个元素，而不是单次连续出现四个元素。这样对吗？ - dingalapadum

@dingalapadum 是的，我想要将相同组中连续项目的最大数量最小化。 - Yohan Liyanage

如果有多个解决方案且这些方案中没有来自同一组的连续项，该如何选择解决方案？ - Dialecticus

每个视频只有一个属性/标签吗？它可以像一个视频属于A类型和C类型一样吗？ - Netham

Answer 1

这与我几年前遇到的一个问题类似：混合液体以避免分层。想法是，如果你要将液体A、B和C混合到一个容器中，你不想只是一个接一个地倒入容器中。相反，你想加入一些A、一些B、一些C等，按照相对比例。

这与在列表中均匀分配项目的问题相同。

假设你有30个A型、20个B型和10个C型，总共60个视频。因此，每隔一个视频，就必须是一个A。每三个视频是一个B，每六个视频是一个C。

因此，A位于0、2、4、6、8等位置。 B位于0、3、6、9、12等位置。而C则位于0、6、12、18等位置。

显然，你必须解决碰撞问题。

我解决这个问题的方法是构建一个包含视频类型及其频率、当前位置（从频率/2开始）的最小堆。因此，堆包含：{A,2,1}，{B,3,1}，{C,6,3}。

为生成您的列表，请从堆中删除最低项并将其添加到列表中。然后，将其频率添加到当前位置，并将其放回堆中。因此，在第一次遍历之后，您已输出了 A，您的堆现在包含：{B,3,1},{A,2,2},{C,6,3}。

输出 B，然后将其加回去，得到：{A,2,2},{C,6,3},{B,3,4} 当然，您也需要保留每个项的计数，每次输出该项时将其递减，并且如果计数达到 0，则不将其添加回堆中。

我大约一年前在我的博客中详细介绍了这个问题。请参见均匀分配项目列表。

就效率而言，该算法具有 O(n log k) 的复杂度，其中 n 是视频总数，k 是视频类型数。

- Jim Mischel

---

只是为了澄清，堆是按“当前位置”值排序的。为了获得O(n log k)的复杂度，在每个步骤中，您只需更新取出并重新插入堆中的单个项目的成本（而我的方法会更新所有类型的成本）。但是，根据堆如何打破平局，输入[3,2,1]可能会给出ABACAB或ABACBA，其中在包装时具有连续的AA。 - Peter Stock

@PeterStock：你说得完全正确。事实证明，如果你调整堆的工作方式，对于某些输入，算法产生的输出结果会不够优化。但是如果你将其调整为针对这些情况创建最佳输出，则会导致其他情况下产生不太优化的结果。我最终得出的解决方案（我还没有在我的博客上发布）是一个妥协，它在某些情况下产生最佳输出结果，在其他情况下产生非常好的输出结果。这在很大程度上取决于你认为什么是“最佳”的。 - Jim Mischel

Answer 2

这是适用于任意类型的算法，而不仅仅是两个类型:

• 将一个类型（例如A、B、C等）称为T。
• 将类型T的项目数量称为N(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是从0开始的，就像数组索引一样。

如果您能够在常数时间内计算出{i}th_gap（可以通过使用另一个计数器来完成），则该算法为线性时间，即O(size*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>");

- Peter Stock

---

一个有趣的想法，虽然我不太清楚你如何在常数时间内找到第 i 个间隙。你展示的代码看起来会是 O(total_items * number_of_types)，因为循环中有 i++。我认为你还应该确保从最频繁的类型开始填充，逐渐降低到最不频繁的类型。话虽如此，你给了我一些改进我目前使用的基于堆的算法的新思路。 - Jim Mischel

你说得对 - i++ 搞砸了它 :( 我正在处理常数时间间隔的问题，维护一个间隔索引数组。我会考虑一下是否可以在没有排序频率输入的情况下工作 - 如果需要对它们进行排序，那么复杂度将为 O(n log n)。 - Peter Stock

干得好。你的代码和我的主要区别在于我显式维护了一个优先队列，而你在每次迭代时计算优先级。本质上是相同的算法。 - Jim Mischel

当我在尝试解决这个问题时，最终编写了一段代码，将单例分组并进行特殊处理。因此，像 [10,1,1] 这样的数组会变成 [10,2]，以便将单例均匀地分布在数组中。否则，它们往往会出现在开头、结尾或正好在中间。 - Jim Mischel

@JimMischel 尽管我的方法的成本重新计算意味着我的算法复杂度比你的更差，但它似乎做了正确的事情，而不需要任何特殊情况。虽然我没有进行非常广泛的测试，你可能会找到一个破坏它的例子。挑战！^_^ - Peter Stock

Answer 3

假设您有A1、A2、...、An和B1、B2、...、Bm。

如果n>m，则至少会连续播放两个A项目（如果播放列表是循环的[一直重复所有内容]）。

您应该首先将A项放在一个循环中。然后在每两个相邻的A项之间放置一个B项。这将隔离下一个A项。如果还有剩余的B项，则放置其余的B项。

如果您想确保第一个和最后一个项目不都是A，则请在开头放置A项目，并在有足够的B项目时在结尾放置B项目。

作为计算算法，对每个A项分配数字（以双精度类型分配数字，以允许它们是有理数），并将这些数字从小到大排序。然后将每个B项分配给相邻A项的平均值。例如：

A1=3 A2=5 A3=10

ArrayA(0)=3

ArrayA(1)=5

ArrayA(2)=10

然后假设您有4个B项目。

 On Error Resume Next

 For n=0 to 3

 ArrayB(n)=(ArrayA(n)+ArrayA(n+1))/2

 Loop

这个循环将尝试调用ArrayA(3)并出现错误，我们将使用on error resume next跳过它。然后，您可以为未分配的B项分配随机数字。

最后，组合两个数组，对它们进行排序。您将获得排序后的数字。通过这些数字，以最优排序方式回调项目。

- user6376109

Answer 4

这个问题看起来并不容易，因为组合的数量很大。如果我没错的话，对于三种类型的视频Na、Nb和Nc，有(Na+Nb+Nc-1)!/Na!Nb!Nc!种可能性。（分子中的-1是因为将循环排列视为相同的情况。）

由于我对组合结构没有清晰的理解，我会尝试以下方法：

• 定义一个评估播放列表分散程度的优点指标。这可以是同一集合中视频之间（循环）距离的总和。

例如：

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

提供

2+2+2+2+2+4+1+1 = 16

并且

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

提供

2+3+1+2+2+2+3+1 = 16

(this is probably an insufficient metric, short distance should be more penalized.)

尝试从可用类型中随机选择序列，直到它们用完，并对序列进行评分。经过多次随机试验后，保留最佳得分。[我会模拟不重复抽取，以便以平衡的方式使用不同类型。]

对于小的N，可以进行详尽的试验。

更新：令人惊讶的是，我建议的简单度量给出了一个恒定值！

- user1196549

---

我发现一种更好的度量方式是比较同类型项目之间距离的标准差。但即使如此，当您有许多（五个或更多）不同类型的视频和不同数量时，这也不是理想的选择。正如您所提到的，穷举搜索很快变得难以处理。 - Jim Mischel

Answer 5

将最大的视频数组分割，并在分割点插入其他元素。

视频类型A：（An=5）[A1，A2，A3，A4，A5]

视频类型B：（Bn=3）[B1，B2，B3]

 1. Choose the Video type having maximum number of instances, in this
    case A.
 2. Divide: (An=5)[A1, A2, A3, A4, A5] / 2 = 2, (An=2)[A1, A2](An=3)[A3, A4, A5]
 3. Now insert one instance of B at the point of division as per step 1, 
    i.e (An=2)[A1, A2](Bn=1)[B1](An=3)(A3, A4, A5)
 4. Now repeat step 2, 3 with (An=2)[A1, A2]  and   (An=3)[A3, A4, A5] and so forth like we do in binary search.
    Final arrangement: (An=1)[A1](Bn=1)[B2](An=1)[A2](Bn=1)[B1](An=2)[A3, A4](Bn=1)[B3](An=1)[A5]

- sameerkn

Answer 6

以下是Java程序，用于排列数组，使得相邻的两个数字不相同。

        public int[] rearrangeArray(int[] arr) {
            int n = arr.length;

            // Store frequencies of all elements
            // of the array
            int[] count = new int[1000]; 
            int[] visited = new int[1000]; 

            for (int i = 0; i < n; i++)
                count[arr[i]]++;

            // Insert all characters with their frequencies
            // into a priority_queue
            PriorityQueue<RandomKey> pq = new PriorityQueue<>(11, new KeyComparator());

            // Adding high freq elements in descending order
            for (int i = 0; i < n; i++) {
                int val = arr[i];

                if (count[val] > 0 && visited[val] != 1)
                    pq.add(new RandomKey(count[val], val));
                visited[val] = 1;
            }

            // 'result[]' that will store resultant value
            int[] result = new int[n];

            // work as the previous visited element
            // initial previous element will be ( '-1' and
            // it's frequency will also be '-1' )
            RandomKey prev = new RandomKey(-1, -1);

            // Traverse queue
            int l = 0;
            while (pq.size() != 0) {

                // pop top element from queue and add it
                // to result
                RandomKey k = pq.peek();
                pq.poll();
                result[l] = k.num;

                // If frequency of previous element is less
                // than zero that means it is useless, we
                // need not to push it
                if (prev.freq > 0)
                    pq.add(prev);

                // make current element as the previous
                // decrease frequency by 'one'
                (k.freq)--;
                prev = k;
                l++;
            }

            return result;
        }



     public class RandomKey {

             int freq;
             int num;

            RandomKey(int freq, int num) {
                this.freq = freq;
                this.num = num;
            }
        }


class KeyComparator implements Comparator<RandomKey> {

    // Overriding compare()method of Comparator
    public int compare(RandomKey k1, RandomKey k2) {
        if (k1.freq < k2.freq)
            return 1;
        else if (k1.freq > k2.freq)
            return -1;
        return 0;
    }
}

- darwin