c# - Find all subsets of a list

Question

I have a list and I need to output each subset of the list

for example a b c d e

would output to

 a
 b
 c  
 d 
 e 
 ab  
 ac  
 ad 
 ae

 abc
 abd 
 abe
 bcd
 bce
 ....
 abcde

I believe the correct term is combination no element should be duplicated on the same line

I was going to attempt this with a series of loops but im not even sure wehre to start

any suggestions?

Answer 1

This will generate the set you want, but in a different order (I sort by alphabet at the end, you'd want to sort by length as well).

You'll end up with:

a ab abc abcd abcde abce ... d de e

So, every possible subset (aside from the empty string), while maintaining the order of the original list.

The idea is to add each element to to a growing list. With every new element, add it first, and then add it to all existing elements.

So, start with 'a'.

Go on to 'b'. Add it to the list. We now have {'a', 'b'}.

Add it to existing elements, so we have 'ab'. Now we have {'a', 'b', 'ab'}.

Then 'c', and add it to existing elements to get 'ac', 'bc', 'abc': {'a', 'b', 'ab', 'c', 'ac', 'bc', abc'}. So forth until we're done.

        string set = "abcde";

        // Init list
        List<string> subsets = new List<string>();

        // Loop over individual elements
        for (int i = 1; i < set.Length; i++)
        {
            subsets.Add(set[i - 1].ToString());

            List<string> newSubsets = new List<string>();

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                string newSubset = subsets[j] + set[i];
                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

        // Add in the last element
        subsets.Add(set[set.Length - 1].ToString());
        subsets.Sort();

        Console.WriteLine(string.Join(Environment.NewLine, subsets));