C# get possible DISTINCT combinations from list

Question

There is possibly already an answer out there and I am simply searching using the wrong terms. I apologize if this is so and ask that you point me to the existing answer if there indeed is one out there.

What I need is to be able to take a list and produce all of the possible distinct combinations from that list. What I mean by distinct is that the same combinations should not show up in different orders.

Here is an example : Say I have a list with the values "One" "Two" and "Three" then I would want the output to = "One","Two","Three","One, Two","Two Three","One Two Three"

I have no interest in the "blank" combination, and I don't want to return the same combination in multiple orders. Most of the code I've found and tried to make work for me has the major flaw that it will return ALL possibilities which include "Two three" and "Three two" which is wrong in my case.

The code I've currently been working to adapt is from another SO question (All Possible Combinations of a list of Values) and looks like this :

  public void GetCombination(System.Collections.Generic.List<string> list)
    {
        Combinations = new List<string>();
        double count = System.Math.Pow(2, list.Count);
        for (int i = 1; i <= count - 1; i++)
        {
            string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
            for (int j = 0; j < str.Length; j++)
            {
                if (str[j] == '1')
                {
                    Combinations.Add(list[j]);
                }
            }
            ///Combinations = found;
        }
    }

Unfortunately I am a novice when it comes to C# and I'm honestly only using it because a co-worker mentioned that it would likely be much faster than my current powershell script which accomplishes what I'm looking for... But takes a very long time to do so.

Thanks in advance for the advice!

You never asked a question, what is the problem you are having. — Scott Chamberlain, Jul 19 '15 at 21:01
The current code does not return the correct output... The question would be, how would one go about finding distinct combos using C#? — Ethan, Jul 19 '15 at 21:02

score 2 · Accepted Answer · edited May 23 '17 at 11:51

Here's an implementation of the code using the power sets answer Martin Smith mentioned:

class Program {
    static void Main(string[] args) {
        // find all possible combinations of this list
        var input = new [] {"One", "Two", "Three"};
        var output = FastPowerSet(input);

        Print(output);
        Console.ReadLine();
    }

    static T[][] FastPowerSet<T>(T[] seq) {
        var powerSet = new T[1 << seq.Length][];
        powerSet[0] = new T[0]; // starting only with empty set
        for (var i = 0; i < seq.Length; i++) {
            var cur = seq[i];
            var count = 1 << i; // doubling list each time
            for (var j = 0; j < count; j++) {
                var source = powerSet[j];
                var destination = powerSet[count + j] = new T[source.Length + 1];
                for (var q = 0; q < source.Length; q++)
                    destination[q] = source[q];
                destination[source.Length] = cur;
            }
        }
        return powerSet;
    }

    static void Print<T>(T[][] seq) {
        for (var i = 0; i < seq.Length; i++) {
            var line = new StringBuilder();
            for (var j = 0; j < seq[i].Length; j++ ) {
                line.AppendFormat("{0}, ", seq[i][j]);
            }
            Console.WriteLine(line);
        }
    }
}

You rock, I think this is going to work perfectly. Thank you very much! — Ethan, Jul 19 '15 at 21:48

C# get possible DISTINCT combinations from list

1 Answers1