Find all subsets of a list

Question

I have a list, and I need to print each subset of the list

e.g. abcde

displays on

a b cde ab ac ad ae abc abd abe bcd bce .... abcde 

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

I was going to do this with a series of loops, but I'm not even sure what you will start

any suggestions?

Answer 1

This will lead to the creation of the set you need, but in a different order (I sort alphabetically at the end, you also want to sort by length).

As a result, you will receive:

a ab alphabet ABCD ABCDE ABCE ... d de e

So, all possible subsets (except the empty string), while maintaining the order of the original list.

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

So start with 'a'.

Go to 'b'. Add it to the list. Now we have {'a', 'b'}.

Add it to existing elements so that 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, until we finish.

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

Answer 2

If all you need is a combination of elements in your original list, you can turn the problem into the following: you have a bit of an array of size N and you want to find all possible options for the elements of the array. For example, if your source list

abcde

then your array may be

0 1 0 0 0

leading to exit

b

or an array may be

1 0 1 1 0

which returns

acd

this is a simple recursion problem that can be solved in O(2^n) time

change pseudo-code adding for recursion algorithm:

 CreateResultSet(List<int> currentResult, int step) { if (the step number is greater than the length of the original list) { add currentResult to list of all results return } else { add 0 at the end of currentResult call CreateResultSet(currentResult, step+1) add 1 at the end of currentResult call CreateResultSet(currentResult, step+1) } } for every item in the list of all results display the result associated to it (ie from 1 0 1 1 0 display acd) 

Answer 3

Here is the code I made. It builds a list of all possible lines from an alphabet from 1 to maxLength in length: (in other words, we calculate the degrees of the alphabet)

  static class StringBuilder<T> { public static List<List<T>> CreateStrings(List<T> alphabet, int maxLength) { // This will hold all the strings which we create List<List<T>> strings = new List<List<T>>(); // This will hold the string which we created the previous time through // the loop (they will all have length i in the loop) List<List<T>> lastStrings = new List<List<T>>(); foreach (T t in alphabet) { // Populate it with the string of length 1 read directly from alphabet lastStrings.Add(new List<T>(new T[] { t })); } // This holds the string we make by appending each element from the // alphabet to the strings in lastStrings List<List<T>> newStrings; // Here we make string2 for each length 2 to maxLength for (int i = 0; i < maxLength; ++i) { newStrings = new List<List<T>>(); foreach (List<T> s in lastStrings) { newStrings.AddRange(AppendElements(s, alphabet)); } strings.AddRange(lastStrings); lastStrings = newStrings; } return strings; } public static List<List<T>> AppendElements(List<T> list, List<T> alphabet) { // Here we just append an each element in the alphabet to the given list, // creating a list of new string which are one element longer. List<List<T>> newList = new List<List<T>>(); List<T> temp = new List<T>(list); foreach (T t in alphabet) { // Append the element temp.Add(t); // Add our new string to the collection newList.Add(new List<T>(temp)); // Remove the element so we can make another string using // the next element of the alphabet temp.RemoveAt(temp.Count-1); } return newList; } } 

Answer 4

something on the lines of the extended while loop:

 <? $testarray[0] = "a"; $testarray[1] = "b"; $testarray[2] = "c"; $testarray[3] = "d"; $testarray[4] = "e"; $x=0; $y = 0; while($x<=4) { $subsetOne[$x] .= $testarray[$y]; $subsetOne[$x] .= $testarray[$x]; $subsetTwo[$x] .= $testarray[$y]; $subsetTwo[$x] .= $subsetOne[$x]; $subsetThree[$x] = str_replace("aa","ab",$subsetTwo[$x]); $x++; } ?> 

Answer 5

This will work with any collection. I changed a little @ Sapp

  static List<List<T>> GetSubsets<T>(IEnumerable<T> Set) { var set = Set.ToList<T>(); // Init list List<List<T>> subsets = new List<List<T>>(); subsets.Add(new List<T>()); // add the empty set // Loop over individual elements for (int i = 1; i < set.Count; i++) { subsets.Add(new List<T>(){set[i - 1]}); List<List<T>> newSubsets = new List<List<T>>(); // Loop over existing subsets for (int j = 0; j < subsets.Count; j++) { var newSubset = new List<T>(); foreach(var temp in subsets[j]) newSubset.Add(temp); newSubset.Add(set[i]); newSubsets.Add(newSubset); } subsets.AddRange(newSubsets); } // Add in the last element subsets.Add(new List<T>(){set[set.Count - 1]}); //subsets.Sort(); return subsets; } 

** And if I have a rowset, I will use it as: