Date: 12/22/05 (Algorithms)    Keywords: web

Hello,

I ran into a combinatorics problem in a website I'm developing. I can't for the life of me figure this one out... I'd be very grateful if anyone could help me with this.

You're given n lists of elements, where an element consists of a unique identifier and a number. These lists are of various lengths and are all sorted from low to high based on the element's number. You want to generate all sequences of elements, where each sequence contains exactly one element from every list. The catch is that you need to generate these sequences in sorted order. The sort value for a sequence is simply the sum of all numbers from the elements in that sequence.

For example if you had just two lists:

List 1: {A-10, B-20}
List 2: {D-1, E-2, F-100}

You would return the following order of sequences:
{A,D}, {A,E}, {B,D}, {B,E}, {A,F}, {B,F}
as that would give you the sort values:
11, 12, 21, 22, 110, 120

I can't just calculate all combinations and then sort them, as my application would typically have billions of combinations and I only need the top 100. I need to do this in sorted order.

Thanks for the help!

Source: http://www.livejournal.com/community/algorithms/68721.html