分区排序列表受到约束

Question

这里有一个问题：

鉴于比如说整数排序列表（你可以假设他们是积极的，如果它使该问题的任何简单），分区列表进入'n'个大小相等的分区（或尽可能相等），但受制于没有任何整数出现多于一个这样的分区的限制。

约束本质上意味着如果你有一个清单 {1,1,2,2}

那么所有的那些都必须在同一组，并且所有2的必须是在同一组。所有1和所有2都可以在一套。但是我们不能在第一个分区中有一个1，在第二个分区中没有第一个。

实施例1：

List: {1,1,2,2,3,3,4,4} 


    Number of partitions to make: 4 

    Answer: {1,1} {2,2} {3,3} {4,4} 

实施例2：（棘手一个）

List: {1,1,2,2,2,3,3,4,4,4,4,4,4,4,4} 

Number of partitions to make : 3 

Answer: {1,1,2,2} {3,3} {4,4,4,4,4,4,4,4} 

    OR: {1,1} {2,2,3,3} {4,4,4,4,4,4,4,4} 

注意这里说的第三分区具有为大小8的因为由于约束条件，所有4都必须在同一个分区中。

可以有许多其他棘手的情况。让我知道是否有人需要更多的例子。

所以问题是什么是最好的方法来解决或解决这个问题？

Answer 1

我能想到的是最简单的解决方案，

1. 首先找到列表中的所有相同的元素（如果你知道前手的范围内使用这样的散列找到他们或计数排序），并维持他们的大小。

2. 现在您将拥有一组重复数字（如{1,1} {2,2}）。完成此步骤后，尝试查找您拥有的列表数量并将它们分组以形成n个分区（如问题说明中指定的那样）。例如。在你最后一个棘手的例子中，最后我们将有4个列表，你需要3个分区。你可以找到2个小列表并将它们组合成1，重复这个直到你达到所需的分区数量。

Answer 2

这是偷偷摸摸的k-partition problem或bin packing problem版本。如果您计算每个元素的出现次数，并将这些计数放入一个多重集中，那么您基本上会试图将这些数字划分为具有相同总和的集合。
如果n = 2，则存在一些伪多项式算法。否则就没有已知的伪多项式算法。 （并且不可能，除非P = NP）
至于如何处理它。如果您选择n，只需将其设置为1并将列表分区。如果你没有，但你有小列表，只需实施暴力解决方案。如果你不选择n，并且你有很长的列表，可以看看贪婪/近似算法，并试着准确定义“尽可能平等”的含义。 （你的意思是最大差异？差异？别的？）
祝你好运。