Ordered combination of List>

Question

Given an arbitrary number of ordered lists

List<int> list1 = new List<int> {1, 1, 2};
List<int> list2 = new List<int> {1, 2, 3, 4};
List<int> list3 = new List<int> {1, 2};
List<int> listN = new List<int> {....,....};

I want to find the combinations of the lists such that sum of each combination are found in ascending order. For example,

{1, 1, 1} = 3, where {1 (1st element of list1), 1 (1st element of list2), 1 (1st element of list3)} 
{1, 1, 1} = 3, where {1 (2nd element of list1), 1 (1st element of list2, 1 (1st element of list3)}
{1, 2, 1} = 4
{1, 1, 2} = 4
{2, 1, 1} = 4
...

The reason for finding the sum in ascending order is so that I have the option of calculating just the first M combinations (e.g. M = 5 above).

My current thinking is to somehow extend finding a combination of all lists, as discussed in Combination of List<List<int>>, by starting with a small subset of the list where the difference between the current and next element is 0, e.g.

List<int> tempList1 = new List<int> {1, 1};
List<int> tempList2 = new List<int> {1};
List<int> tempList3 = new List<int> {1};

and finding all combinations, then adding to the list the next element with the smallest difference

List<int> tempList1 = new List<int> {1, 1, 2};
List<int> tempList2 = new List<int> {1, 2};
List<int> tempList3 = new List<int> {1, 2};

and building the solution set from there.

Is this possible, and is there a better way to do this?

Do you mean the sum of each combination of *summed* lists? i.e - you wish to sum all the numbers in each list, then, find all the combinations of adding said totals to each other? — Dave Bish, Dec 21 '12 at 17:00
Not quite. I want to take one element from each list1, list2, ... listN and sum them, and order these said totals. I'll try to clarify this in my example in the original post. — wave, Dec 21 '12 at 17:04
In your example, there are two more "ways" to get the sum `4` because `list1` has two identical elements (two `1`s), so I think your question should reflect that. — Jeppe Stig Nielsen, Dec 21 '12 at 17:53

score 0 · Answer 1 · answered Dec 21 '12 at 17:06

Computing a single item is not expensive, but keeping all the results in memory and ordering them may be if the number of items is large. However, computing combinations doesn't seem to help much for solving the task, if I understand it crrectly.

Edit: I didn't see the clarification about the combinations when I started writing my response. Either way, the following algorithm can also be used if you have a generator for the different combinations. I'm not sure whether there is a generic solution to generate only the wanted sums.

Let's say N is the count of items and M is the count of results which you want to get. For the following to make sense I assume that N >> M (e.g. is much larger).

I'd then use the following algorithm:

Create a result list for holding up to M items.
Go through all N items.
- For each item, compute the total
- Insert the total in the result list so that the order is correct (a binary search will probably be a fine algorithm to use for doing that)
- Trim the result list to be no more than M items after the insert (the inserted item, or previously iserted items, will fall out depending on their computation result)
You now have the top M items, ordered descending

Note that you can easily make the above algorithm stable in relation to the order of the original N items if you with to do so.

Dave Bish · Answer 2 · 2012-12-21T17:39:01.910

Try this:

List<int> list1 = new List<int> { 1, 1, 2 };
List<int> list2 = new List<int> { 1, 2, 3, 4 };
List<int> list3 = new List<int> { 1, 2 };

var combinations = list1
    .SelectMany(x => list2, (a, b) => new { a, b })
    .SelectMany(x => list3, (combined, c) => new { a = combined.a, b = combined.b, c })
    .Select(comb => new{ Sum = comb.a + comb.b + comb.c, Combination = new List<int>{comb.a, comb.b, comb.c}})
    .OrderBy(summed => summed.Sum);

╔═════════════╦═════╗
║ Combination ║ Sum ║
╠═════════════╬═════╣
║ 1,1,1       ║   3 ║
║ 1,1,1       ║   3 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
║ 1,1,2       ║   4 ║
║ 1,2,1       ║   4 ║
╚═════════════╩═════╝

edit: Cleaned up a bit

Ordered combination of List>

2 Answers2