Get all subsets of a collection
algorithm, c#, set, subset
Solution
This is a basic algorithm which i used the below technique to make a single player scrabble word solver (the newspaper ones).
Let your set have `n` elements. Increment an integer starting from 0 to `2^n`. For each generater number bitmask each position of the integer. If the `i` th position of the integer is `1` then select the `i` th element of the set. For each generated integer from `0` to `2^n` doing the above bitmasting and selection will get you all the subsets.
Here is a post: http://phoxis.org/2009/10/13/allcombgen/
Problem
I am trying to create a method that will return all subsets of a set. For example if I have the collection `10,20,30` I will like to get the following output ``` return new List<List<int>>() { new List<int>(){10}, new List<int>(){20}, new List<int>(){30}, new List<int>(){10,20}, new List<int>(){10,30}, new List<int>(){20,30}, //new List<int>(){20,10}, that substet already exists // new List<int>(){30,20}, that subset already exists new List<int>(){10,20,30} }; ``` because the collection can also be a collection of strings for instance I want to create a generic method. This is what I have worked out based on this solution. ``` static void Main(string[] args) { Foo<int>(new int[] { 10, 20, 30}); } static List<List<T>> Foo<T>(T[] set) { // Init list List<List<T>> subsets = new List<List<T>>(); // Loop over individual elements for (int i = 1; i < set.Length; 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 tempList = new List<T>(); tempList.Add(subsets[j][0]); tempList.Add(subsets[i][0]); var newSubset = tempList; newSubsets.Add(newSubset); } subsets.AddRange(newSubsets); } // Add in the last element //subsets.Add(set[set.Length - 1]); //subsets.Sort(); //Console.WriteLine(string.Join(Environment.NewLine, subsets)); return null; } ``` Edit Sorry that is wrong I still get duplicates... ``` 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; } ``` Then I could call that method as: