Find sum of number in multiple sets using exactly one number of each set

Question

Background

Hi, I'm trying to solve a programming problem and I'm stuck on the following problem:

Assume you have multiple lists of numbers. All are sorted in decreasing order. You now have to take exactly one number from each list to make the biggest possible sum.

So far so easy, to solve this you could just take the first number of each list and you're done.

But now, I need the second-largest sum while still using exactly one number from each list. To achieve this, I would take the first element in each list but for the list which has the least difference between the first and second number the second number will be used.

This is still pretty doable.

The Problem

But I need an Iterator over every possible sum using exactly one number of each list sorted in decreasing order.
For performance reasons, it isn't possible to just compute every sum and then sort it. The algorithm must already provide the sums in decreasing order. If there are multiple combinations for a sum then the sum must be returned multiple times.

Additional Requirements

The Iterator should be lazy (only calculate the next sum when required).
The Lists are already lazy, which means you should require as few values as possible to calculate the fitting sum.

Example

For the Lists:

List 1: [5, 2, 1]
List 2: [10, 2]
List 3: [6, 1]

The Iterator then should return:

[5, 10, 6] = 21
[2, 10, 6] = 18
[1, 10, 6] = 17
[5, 10, 1] = 16
[5,  2, 6] = 13
[2, 10, 1] = 13
[1, 10, 1] = 12
[2,  2, 6] = 10
[1,  2, 6] = 9
[5,  2, 1] = 8
[2,  2, 1] = 5
[1,  2, 1] = 4

Comment

I don't need code as an answer to my question (you're still welcome to provide it if it helps to explain). What I'm looking for are ideas to solve this, or solutions that I can implement myself.

Thanks in advance!

Answer 1

First of all, Thanks to wlui155 for the help.

For Anyone interested, I coded a BFS algorithm that acts as follows:

Definitions:
Entry: Struct containing indices of used numbers and sum
BSet: Ordered set which can only contain unique Entries

Algorithm:

1. Pop Entry with biggest sum from BSet
2. Create a clone for each list
3. Advance in each clone a different index by one
4. Put new entries in BSet
5. Print current Entry
6. Goto 1.

Now you only have to ensure that no entry appears again after you've popped it. This can be ensured with a separate set containing all combinations for the current sum. Once the current sum gets smaller this set can be cleared.

If you have ideas to improve this, you're welcome to tell me.