Good algorithm for combining items from N lists into one with balanced distribution?

Question

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.

Answer 1

You could simply combine the three lists into a single list and then UNSORT that list. An unsorted list should achieve your requirement of 'evenly-distributed' without too much effort.

Here's an implementation of unsort: http://www.vanheusden.com/unsort/.

Answer 2

I'm thinking of a divide and conquer approach. Each iteration of which you split all the lists with elements > 1 in half and recurse. When you get to a point where all the lists except one are of one element you can randomly combine them, pop up a level and randomly combine the lists removed from that frame where the length was one... et cetera.

Something like the following is what I'm thinking:

- 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

Answer 3

A quick suggestion, in python-ish pseudocode:

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)

This should distribute elements from shorter lists more evenly than the other suggestions here.

Answer 4

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 :)

Answer 5

First, this answer is more of a train of thought than a concete solution.

OK, so you have a list of 3 items (A1, A2, A3), where you want A1 to be somewhere in the first 1/3 of the target list, A2 in the second 1/3 of the target list, and A3 in the third 1/3. Likewise you want B1 to be in the first 1/2, etc...

So you allocate your list of 10 as an array, then start with the list with the most items, in this case C. Calculate the spot where C1 should fall (1.5) Drop C1 in the closest spot, (in this case, either 1 or 2), then calculate where C2 should fall (3.5) and continue the process until there are no more Cs.

Then go with the list with the second-to-most number of items. In this case, A. Calculate where A1 goes (1.66), so try 2 first. If you already put C1 there, try 1. Do the same for A2 (4.66) and A3 (7.66). Finally, we do list B. B1 should go at 2.5, so try 2 or 3. If both are taken, try 1 and 4 and keep moving radially out until you find an empty spot. Do the same for B2.

You'll end up with something like this if you pick the lower number:

C1 A1 C2 A2 C3 B1 C4 A3 C5 B2

or this if you pick the upper number:

A1 C1 B1 C2 A2 C3 A3 C4 B2 C5

This seems to work pretty well for your sample lists, but I don't know how well it will scale to many lists with many items. Try it and let me know how it goes.

Answer 6

• Make a hash table of lists.
• For each list, store the nth element in the list under the key (/ n (+ (length list) 1))
• Optionally, shuffle the lists under each key in the hash table, or sort them in some way
• Concatenate the lists in the hash by sorted key