List items calculation

Question

Let's say I have a list / array of integers, i.e:

{1, 2, 3, 4}

Is there a way to get every single possible combination of additions and add them to another list / array?

Like this:

1+2, 1+3, 1+4, 
2+3, 2+4,
3+4,

1+2+3, 1+2+4, 1+3+4,
2+3+4,

1+2+3+4

So the end-result would be (without duplicates):

{3, 4, 5, 6, 7, 8, 9, 10}

In your example you wrote your calculation down in a structured way. This structure is your starting point of finding an algorithm to do this calculation. — Peter Bruins, Apr 05 '17 at 07:27
@BugFinder I have tried it with for loops and foreach loops, also nested loops, but I still couldn't figure out a way to do it. — AleksanderCH, Apr 05 '17 at 07:43
@AleksanderRassasse Its as simple as.. As a human, how would you structure to ensure you had done one of each.. you grouped them, so thats a really good start.. Do you not see a programming pattern in that list? — BugFinder, Apr 05 '17 at 07:45
@BugFinder I obviously see a pattern, but I don't know how to program it. That's why I posted this question in the first place. — AleksanderCH, Apr 05 '17 at 07:56
@AleksanderRassasse So, write down in human language how you worked out that list.. that becomes your pseudo code, then take the bits you know how to do, in c#, and replace them, and see what you have left.. The art of coding is exactly this, boiling the logic down to what to write. — BugFinder, Apr 05 '17 at 07:59
Sometimes when you are stuck with a problem it can help to solve an easier version of it first. Or just solve one part of it. Like: How would you calculate only the two integer permutations? How would your solution differ if you only had an array of two integers? What if you had only three? — Kempeth, Apr 05 '17 at 08:22
As you semms to see some algo about it, their is a great source here: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — Drag and Drop, Apr 05 '17 at 09:17

Leze · Answer 1 · 2017-04-12T10:11:30.450

2

With more specific to int list you can do that

   static List<int> GetCombination(List<int> list, List<int> combinations, int sumNum, bool addNumberToResult = false)
    {
        if (list.Count == 0) {
            return combinations;
        }

        int tmp;

        for (int i = 0; i <= list.Count - 1; i++) {
            tmp = sumNum + list[i];
            if(addNumberToResult){
                combinations.Add(tmp);
            }
            List<int> tmp_list = new List<int>(list);
            tmp_list.RemoveAt(i);
            GetCombination(tmp_list,combinations,tmp, true);
        }

        return combinations;
    }

and to call it simply do

List<int> numbers = new List<int>(){1,2,3,4,5};
List<int> possibleCombination = GetCombination(numbers, new List<int>(), 0);

and to remove duplicate

possibleCombination.Distinct()

If you want it orderer you can call

possibleCombination.Distinct().OrderBy(itm => itm)

or

possibleCombination.Distinct().OrderByDescending(itm => itm)

C# fiddle

Edit : As Pierre rightly pointed out, the code did not stick to the question, I corrected accordingly, adding an parameters for adding or not the numbers to the result list.

edited Apr 12 '17 at 10:11

answered Apr 05 '17 at 09:45

Leze

739
5
24

The test value `{1, 2, 3, 4}` do not give the expected result, sending `new List(), 0` to a function is a bit weird. – Drag and Drop Apr 12 '17 at 08:54
I run it again with `{1, 2, 3, 4}` and out put are `1, 2, 3, 4, 5, 6, 7, 8, 9, 10` as excepted, what is wrong? I know that sending new List in constructor seems to be a bit weird, here is just the faster way to use the function, you can init the list before calling GetCombination and pass it as parameters, but for recurring call you need it as parameters. Any improve can be made of course. – Leze Apr 12 '17 at 09:32
From op question : "So the end-result would be (without duplicates): `{3, 4, 5, 6, 7, 8, 9, 10}`" Op is ingnoring the "singleton" subset `{ {1}, {2}, {3}, {4} }`. – Drag and Drop Apr 12 '17 at 09:38
And Yes the constructor thing was just a minor thing. – Drag and Drop Apr 12 '17 at 09:39
you're right, i missing the thing... – Leze Apr 12 '17 at 09:57
Corrected accordingly yours observations Pierre, thanks to pointing me to it. – Leze Apr 12 '17 at 10:12

score 0 · Accepted Answer · edited May 23 '17 at 12:32

Based on this great answer here is a version that will allow you to eliminate the "small subset"(*)

public static List<List<T>> GetCombination<T>(List<T> inputList, int minimumItems = 1)
{
    int count = (int)Math.Pow(2, inputList.Count) - 1;
    List<List<T>> result = new List<List<T>>(count + 1);

    if (minimumItems == 0)
        result.Add(new List<T>());

    for (int i = 1; i <= count; i++)
    {
        List<T> combinason = new List<T>(inputList.Count);
        for (int j = 0; j < inputList.Count; j++)
        {
            if ((i >> j & 1) == 1)
                combinason.Add(inputList[j]);
        }

        if (combinason.Count >= minimumItems)
            result.Add(combinason);
    }

    return result;
}

Result:

>> { {1,2}, {1,3}, {2,3}, {1,2,3}, {1,4}, {2,4},
>>   {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}   }

From here a simple .Sum() on the subset:

Subsets.ForEach( s => result.Add(s.Sum()) );

As you wanted to clear every duplicate in the list:

DoublonList.Distinct();

C# fiddle

ps: (*) Can't find the word in english for groupe of only one element

List items calculation

2 Answers2