将N个列表中的项目组合成一个平衡分布的好算法?

1. 拿一份成员最多的名单。这将是目的地列表。

2. 然后选取成员数量次多的列表。

3. 将目标列表长度除以较小的长度,得到大于1的分数值。

4. 对于第二个列表中的每个项目,维护一个浮点计数器。将上一步计算的值相加,并在数学上将其四舍五入到最接近的整数(保持原始浮点计数器不变)。将其插入目标列表中的此位置,并将计数器递增1以计算它。对第二个列表中的所有列表成员重复此操作。

5. 对所有列表重复步骤2-5。

编辑:这也有O(n)的优点,这总是很好:)

实施 安德鲁·罗林斯的回答:

public List<String> equimix(List<List<String>> input) {

  // sort biggest list to smallest list
  Collections.sort(input, new Comparator<List<String>>() {
     public int compare(List<String> a1, List<String> a2) {
        return a2.size() - a1.size();
     }
  });

  List<String> output = input.get(0);

  for (int i = 1; i < input.size(); i++) {
     output = equimix(output, input.get(i));
  }

  return output;
}

public List<String> equimix(List<String> listA, List<String> listB) {

  if (listB.size() > listA.size()) {
     List<String> temp;
     temp = listB;
     listB = listA;
     listA = temp;
  }

  List<String> output = listA;

  double shiftCoeff = (double) listA.size() / listB.size();
  double floatCounter = shiftCoeff;

  for (String item : listB) {
     int insertionIndex = (int) Math.round(floatCounter);
     output.add(insertionIndex, item);
     floatCounter += (1+shiftCoeff);
  }

  return output;
}

首先,这个答案更多的是一个思路,而不是一个自负的解决方案。

好的,您有一个包含3个项目(A1、A2、A3)的列表,其中A1位于目标列表的前1/3,A2位于目标列表第二1/3,A3位于第三1/3。同样,你希望B1位于前1/2,以此类推。。。

因此,您将10的列表分配为一个数组,然后从包含最多项目的列表开始,在本例中为C。计算C1应该落下的位置(1.5)将C1放在最近的位置(在本例下为1或2),然后计算C2应该落下(3.5),并继续此过程,直到没有更多的Cs为止。

然后按照项目数量倒数第二的列表进行操作。在这种情况下,A.计算A1的位置(1.66),所以先尝试2。如果你已经把C1放在那里,试试1。对A2(4.66)和A3(7.66)执行相同的操作。最后,我们做列表B.B1应该是2.5,所以尝试2或3。如果两者都服用,尝试1和4,并继续径向向外移动,直到找到一个空位。对B2做同样的事情。

如果你选择较低的数字,你最终会得到这样的结果:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

或者,如果你选择上面的数字:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

这似乎对你的示例列表很有效,但我不知道它能很好地扩展到包含许多项目的许多列表。试试看,让我知道进展如何。

• 制作一个列表哈希表。
• 对于每个列表,将列表中的第n个元素存储在键下 (/ n (+ (length list) 1))
• 可选地,对哈希表中每个键下的列表进行洗牌,或以某种方式对其进行排序
• 按排序键连接哈希中的列表

我正在考虑一种分而治之的方法。每次迭代,您都会用元素拆分所有列表>1分之一,重复出现。当你到达除一个列表外的所有列表都是一个元素的点时,你可以随机组合它们,弹出一个级别,并随机组合从长度为1的帧中删除的列表。…等等。

以下是我的想法:

- filter lists into three categories
    - lists of length 1
    - first half of the elements of lists with > 1 elements
    - second half of the elements of lists with > 1 elements
- recurse on the first and second half of the lists if they have > 1 element
    - combine results of above computation in order
- randomly combine the list of singletons into returned list 

您可以简单地将三个列表组合成一个列表,然后取消该列表的排序。一个未排序的列表应该能够满足你“均匀分布”的要求,而不需要太多努力。

以下是unsort的实现: http://www.vanheusden.com/unsort/ .

一个简短的建议,用python风格的伪代码:

merge = list()
lists = list(list_a, list_b, list_c)
lists.sort_by(length, descending)

while lists is not empty:
    l = lists.remove_first()
    merge.append(l.remove_first())
    if l is not empty:
        next = lists.remove_first()
        lists.append(l)
        lists.sort_by(length, descending)
        lists.prepend(next)

这应该比这里的其他建议更均匀地分布较短列表中的元素。