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

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 of members.

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 2

Implementation of Andrew Rollings' answer:

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;
}

Answer 3

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.