Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
336 views
in Technique[技术] by (71.8m points)

c# - Find all subsets of a list

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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));

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...