Custom Combination List <List <int>>

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 combinations of lists so that the sum of each combination is in ascending order. For instance,

 {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 that I have the ability to calculate only the first combinations of M (for example, M = 5 above).

My current thinking is to somehow expand the search for all combinations, as described in List Combinations <List <int → , starting with a small subset of the list, where the difference between the current and the next item is 0, for example

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

and find all the combinations, and then add to the list the next element with the least 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 a set of solutions from there.

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

Answer 1

Calculation of one element is not expensive, but you can save all the results in memory and order them if the number of elements is large. However, computational combinations do not seem to help much in solving the problem, if I understand it correctly.

Edit: I didn’t see any explanation of the combinations when I started writing my answer. In any case, the following algorithm can also be used if you have a generator for different combinations. I am not sure if there is a general solution for generating only the desired amounts.

Suppose N is the number of elements and M is the number of results you want to get. In order to make sense, I assume that N → M (for example, a lot more).

Then I would use the following algorithm:

• Create a list of results to place items M.
• Go through all N items.
  • For each element, calculate the total
  • Paste the total in the list of results so that the order is correct (binary search will probably be a good algorithm for this)
  • Trim the list of results no more than M elements after insertion (the inserted element or previously transferred elements will drop out depending on the result of their calculation)
• Now you have the top M items in descending order

Please note that you can easily make the above algorithm stable with respect to the order of the original N elements if you do.

Answer 2

Try the following:

 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: Removed a bit