Tono Nam Tono Nam - 29 days ago 7
C# Question

Get all subsets of a collection

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:

enter image description here

Answer

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/

Comments