Alex Rivera | Logout

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

Asked 2008-12-05T19:26:12.537
11

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.

algorithm list
Edit
Report

1 Answer

-1

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.

answered 2008-12-05T19:42:25.203

Your Answer