良好的算法结合从N个列表中的项目为一个与均衡分布？ [英] Good algorithm for combining items from N lists into one with balanced distribution?

问题描述

让我们说我有以下三个列表

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

我想将它们合并成一个单一的列表，每个列表中的项目，如均匀分布尽可能八九不离十是这样的：

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

我使用.NET 3.5 / C＃，但我正在寻找更多的如何处理它，然后具体的code。

编辑：我需要保持从原来的列表中元素的顺序

。

解决方案

1. 以列表的副本与大多数成员。这将是在目的地列表

2. 然后将这个列表与下一个最大数。

3. 划分目的地列表长度由较小的长度，得到大于一个的分数值

4. 对于第二个列表中的每个项目，保持一个浮点计数器。添加在previous步骤计算的值，数学舍入为最接近的整数（保持原浮动柜台完好无损）。把它插入到目标列表在这个位置上，并以1递增计数器来解释它。重复第二列表中的所有列表成员。

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

编辑：这具有O（n）的优势为好，这总是好的：）

Let's say I have the three following lists

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

I'd like to combine them into a single list, with the items from each list as evenly distributed as possible sorta like this:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

I'm using .NET 3.5/C# but I'm looking more for how to approach it then specific code.

EDIT: I need to keep the order of elements from the original lists.

解决方案

1. Take a copy of the list with the most members. This will be the destination list.

2. Then take the list with the next largest number.

3. divide the destination list length by the smaller length to give a fractional value of greater than one.

4. For each item in the second list, maintain a float counter. Add the value calculated in the previous step, and mathematically round it to the nearest integer (keep the original float counter intact). Insert it at this position in the destination list and increment the counter by 1 to account for it. Repeat for all list members in the second list.

5. Repeat steps 2-5 for all lists.

EDIT: This has the advantage of being O(n) as well, which is always nice :)

这篇关于良好的算法结合从N个列表中的项目为一个与均衡分布？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！