Get distinct combinations of numbers

Question

The below code returns all distinct combinations based on the logic that 1,2,3 = 3,2,1 = 2,3,1, so it only returns 1 instance of that set of numbers.

public void GetPowersets()
{
    List<int> ints = new List<int>()
    {
        1,2,2,3,3
    };

    var results = GetPowerSet(ints);


    List<String> combinations = new List<String>();
    foreach (var result in results)
    {
        StringBuilder sb = new StringBuilder();
        foreach (var intValue in result.OrderBy(x => x))
        {
            sb.Append(intValue + ",");
        }
        combinations.Add(sb.ToString());
    }

    string c1 = string.Join("|", combinations.ToArray()).Replace(",|", "|");
    //c1 = "|1|2|1,2|2|1,2|2,2|1,2,2|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3,3|1,3,3|2,3,3|1,2,3,3|2,3,3|1,2,3,3|2,2,3,3|1,2,2,3,3,"

}

public IEnumerable<IEnumerable<int>> GetPowerSet(List<int> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
                 select
                     from i in Enumerable.Range(0, list.Count)
                     where (m & (1 << i)) != 0
                     select list[i];
}

This is the end result I am trying to achieve: (no duplicate rows of combinations: duplicate = 3,2,1 and 3,2,1 are the same thing. but 1,2,3 and 3,2,1 are NOT the same thing and both should be in the end result)

1
2
3
1,2
1,3
2,1
2,3
2,2
3,1
3,2
3,3
1,2,3
1,2,2
1,3,2
1,3,3
2,1,3
2,1,2
2,3,1
2,3,2
2,3,3
2,2,1
2,2,3
3,1,2
3,1,3
3,2,1
3,2,2
3,2,3
3,3,1
3,3,2
1,2,3,2
1,2,3,3
1,2,2,3
1,3,2,2
1,3,2,3
1,3,3,2
2,1,3,2
2,1,3,3
2,1,2,3
2,3,1,2
2,3,1,3
2,3,2,1
2,3,2,3
2,3,3,1
2,3,3,2
2,2,1,3
2,2,3,1
2,2,3,3
3,1,2,2
3,1,2,3
3,1,3,2
3,2,1,2
3,2,1,3
3,2,2,1
3,2,2,3
3,2,3,1
3,2,3,2
3,3,1,2
3,3,2,1
3,3,2,2
1,2,3,2,3
1,2,3,3,2
1,2,2,3,3
1,3,2,2,3
1,3,2,3,2
1,3,3,2,2
2,1,3,2,3
2,1,3,3,2
2,1,2,3,3
2,3,1,2,3
2,3,1,3,2
2,3,2,1,3
2,3,2,3,1
2,3,3,1,2
2,3,3,2,1
2,2,1,3,3
2,2,3,1,3
2,2,3,3,1
3,1,2,2,3
3,1,2,3,2
3,1,3,2,2
3,2,1,2,3
3,2,1,3,2
3,2,2,1,3
3,2,2,3,1
3,2,3,1,2
3,2,3,2,1
3,3,1,2,2
3,3,2,1,2
3,3,2,2,1

I wanted to change that logic so that it returns ALL instances of all number sets.

Below is my for loop implementation of this logic.

public List<List<int>> GetAllCombinationsOfAllSizes(List<int> ints)
{
    List<List<int>> returnResult = new List<List<int>>();

    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = new List<int>();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

    return returnResult;
}
public void _GetAllCombinationsOfAllSizes(List<int> ints, List<int> growingList, ref List<List<int>> returnResult)
{
    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = growingList.ToList();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

}

The above solution to my problem is slow and prone to running out of memory. This seems to happen when the number set gets too large, like when passing in 15 or more numbers.

I am looking for a review on the above posted code. I am specifically interested in where I went wrong in terms of performance, and how I could improve that. I am open to all sorts of suggestions and criticisms on my code and implementation. Additionally, I am curious if there is a way to utilize Linq to improve my above code.

Answer 1

Let's talk algorithms, and complexity..... and what the actual problem is that you are trying to solve.

Background

Three concepts: distinct, permutation, and combination

Distinct

Distinct values are each unique within their peers. In your case, you have the input values {1, 2, 2, 3, 3}. The distinct set is just {1, 2, 3}. There are 5 input values, there are 3 distinct values.

Now, the 'original' problem extended this concept of distinct to apply to ordered sets as well. So, with the combinations for {1, 2, 2, 3, 3}, two of the possible combinations are where just the second member is in the result, and just the third member is in the result... these are the combinations {2} and {2}, but they are different 2's. The original code discards the second combination as a duplicate of the first.

Your goal is to keep both of them, since they are 'different' 2 values.

Permutations

Permutations are about order. What ways are there to order a set of data. There is no concept of what the data is, only where the data is. With the input data {1, 2, 3}, what are the permutations?

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

There can be a lot of permutations, and the numbers get large fast.

The actual formula is a factorial, as in \$n!\$ where \$n\$ is the number of values in the set. If there is one member, there is only one permutation.

If there are two, then there are two permutations. Now, the way to visualize it, is that, we know there are two ways to arrange two members.... with three members, we start building permutations... take the first member from the set, and there are 2 ways to arrange the remaining 2 members. Then take the second member from the set, and there are two ways to arrange the remaining 2. Finally, take the last member from the set, and there are two ways to arrange the remaining 2. In other words, there are \$3 \times 2\$ permutations. If we reduce the logic down to just one member in the set, then the actual sequence is \$3 \times 2 \times 1\$. Then, if we add a fourth member, it becomes \$4 \times 3 \times 2 \times 1\$

Factorial numbers get large, fast. So, the following factorials are 'realistic' (for an arbitrary definition of realistic):

1. 1
2. 2
3. 6
4. 24
5. 120
6. 720
7. 5040
8. 40320
9. 362880
10. 3628800
11. 39916800
12. 479001600
13. 6227020800 <---- larger than 32-bit Integer
14. 87178291200
15. 1307674368000
16. 20922789888000
17. 355687428096000
18. 6402373705728000
19. 121645100408832000
20. 2432902008176640000 <---- larger than 64-bit integer

Calculating the permutations for even a moderate (say 10) sized dataset is a large undertaking.... (>3.5million permutations)

Combinations

Combinations are about whether data is in the set, or not. Combinations consist of a set of conditions: either the data is in, or it is not. Where the data is, in the output set, is not relevant for combinations, only that it is there. So, If you have the input values {1, 2, 3}, then the combinations are:

1. {}
2. {1}
3. {2}
4. {3}
5. {1, 2}
6. {1, 3}
7. {2, 3}
8. {1, 2, 3}

The math behind combinations is relatively simple. There are \$n\$ members in an input set, each member is either in the output set, or not in the output set. Now, because there is a 'binary' condition (either in, or out), you can think of the problem as follows:

If there is just one input member, then that member is either in the set, or not. There are 2 combinations, the empty set, and the set with that one member.

If we add a second input member, then we can have the same two combinations of the first member, but then we can also add the second member to the output, and get another two combinations. As follows (for the input data {a, b}):

1. [ ] <-- empty
2. [ b]
3. [a ]
4. [a b]

If we add a third input member, we can have the same 4 combinations above, but then we can also have it with the third member.

There is a pattern here, each time we add a member, we double the number of combinations. Now, in computer science, it happens that there is a very convenient system we can use to help with this... it's called an 'integer'. Consider an input dataset with 3 members.... Now, consider a 3-bit integer. Let's count with a 3-bit integer:

000
001
010
011
100
101
110
111

This bit representation of our three-bit number shows the possible combinations! If we take an input data set of {a, b, c}, and then use the bits in the above counting to indicate whether the data member is 'in' the combination, or 'out', then you can do the following:

000  
001    c
010   b 
011   bc
100  a  
101  a c
110  ab 
111  abc

To read the above table, you need to say, 'if the bit in the same position as the input data is set, then include the value in the input data in the combination'.

This leads on to the number of combinations that are possible, and we can borrow from the binary numbers again. The number is \$2^n\$ where \$n\$ is the number of members in the input set.

So, with 10 input members, there`s \$2^{10}\$ combinations, or 1024. With 16 input values, that would be 65536 combinations... and so on.

What is important here is that you are essentially limited to a small data set... but not quite as small as the factorial problem.

Putting it Together.

Your problem, as stated, has the three components. One of them is duplicates, but you want to keep the duplicates, so we can ignore that. Then, the code identifies all the combinations that are possible.... and then, for each combination, it outputs all the permutations.

Note, that it skips the first combination (it is relatively common to ignore the empty data set).

How many results should there be? for an input set of 5 members? Well, there's 31 combinations (\$2^5 - 1\$), 5 have 1 member, 10 have 2 members, 10 have 3 members, 5 have 4 members, and one has 5 members. Each of those combinations can be permuted. How many permutations?

5  * 1  (5 combinations have 1 permutation each)
10 * 2  (10 combinations have 2 permutations each)
10 * 6
5  * 24
1  * 120 (1 combination has 120 permutations).

or ... 153 combinations and permutations..... in total (154 if you count the empty-set).

Now, with 15 members in the input set.... you are looking at.... say, 1307674368000 permutations for just the one combination where you have all 15 input members.....

Then, there are 15 combinations with 14 members, so, that's another 15 x 87178291200 permutations.

and so on.....

As you can see, the results are getting quite 'large'.

You have to scale back your expectations....

But, there are ways, with both combinations, and permutations, to produce the valid results in a 'streaming' or 'yielded' fashion, where you do not need to output all the results in memory at once. Even with these mechanisms, the time required to calculate so many results is substantial.... so, practically, you would be limited to at most 10 or so members in your set. Even then I expect it to take days to calculate/output all the results...

For your interest, I have written a Java program that calculates the combination members as an array for an arbitrary number of inputs. It 'yields' the result in the form of a Java iterator. You should be able to read the code, and apply it, if you want.

Have a look at the main method for the usage..... This just solves the combinations part of the problem, not the permutations. For each of these combinations, you would have to permute the results too.

Answer 2

Pasting your code exactly as is into my IDE, ReSharper gives the following warnings and suggestions:

List<List<int>> returnResult = new List<List<int>>();

Use implicitly typed local variable declaration

I'd also rename returnResult to just result, so:

var result = new List<List<int>>();

var newList = new List<int>();
newList.Add(number);

Use collection initializer

Each item in a collection initializer calls Add on the list, so this is equivalent:

var newList = new List<int> {number};

listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

Replace with single call to First(..)

I'd ignore that suggestion, as this SO question/answer demonstrates a performance improvement with .Where().First() over .First().

if (listMinusOneObject.Count() > 0)

Use method Any()

That I'd do. Count() will iterate every item in the list, only to compare against 0; Any() will return true as soon as it finds 1 item in the list:

if (listMinusOneObject.Any())

When a foreach loop can be converted to a LINQ statement, ReSharper is very good at pointing it out. So I replaced your for loops with foreach loops (removed the number declaration/assignment):

var distinctInts = ints.Distinct().ToList();
foreach(var number in distinctInts)
{
    var newList = new List<int> {number};
    returnResult.Add(newList);

    var listMinusOneObject = ints.Select(x => x).ToList();
    listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

    if (listMinusOneObject.Any())
    {
        _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
    }
}

and

var distinctInts = ints.Distinct().ToList();
foreach (var number in distinctInts)
{
    var newList = growingList.ToList();
    newList.Add(number);
    returnResult.Add(newList);

    var listMinusOneObject = ints.Select(x => x).ToList();
    listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

    if (listMinusOneObject.Any())
    {
        _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
    }
}

And as I expected, ReSharper doesn't suggest anything. Why is that so?

LINQ stands for Language-INtegrated Query. Querying objects does not usually involve side-effects, and this is precisely what's going on in your loops' bodies: you're not querying a List<int>, you're iterating it. A foreach loop does that.

---

That was just cosmetics and minor adjustments (some of which may have a positive impact on performance); there's a lot to be said about your algorithm, I'll leave that to another reviewer.

---

I played with your code quite a bit, and found a way to help performance a bit - this won't help the OutOfMemoryException with larger sets, but I got {1,2,3} to run twice faster by replacing these lines:

   var listMinusOneObject = ints.Select(x => x).ToList();
   listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

With this (seems to produce the same output):

var listMinusOneObject = ints.Where(x => x != number);

and then changing the signatures to take an IEnumerable<int> instead of a List<int>: the ToList() call you have there is costing quite a lot.

Answer 3

I'm not sure how your algorithm works, but I can give you a couple of suggestions about modifications that you should to do.

First of all, I think that you should have separate methods. One for returning all possible combinations of a fixed size and one for all possible combinations of all sizes.

Secondly, you should return IEnumerable instead of List. For two reasons:

1. IEnumerable is an interface and not a implemented class.
2. By returning IEnumerable you can use the lovely yield keyword (Really, you should be happy you have that - Java doesn't).

By yield-ing your results, you won't consume any extra memory at all. There is a lot of magic going on behind the scenes. The point is: When you use yield, your method will be processed on an on-demand basis. It will return something, process that, return something more, process that, return something more, process that, and so on.

I hope this will help you on your way to rewriting this method.