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?
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));
if all you need are combinations of the elements in your original list, you can transform the problem into the following: you have a bit array of size N, and you want to find all possible choices for the elements of the array. For example, if your original list is
a b c d e
then your array can be
0 1 0 0 0
which results in an output of
b
or the array can be
1 0 1 1 0
which returns
acd
this is a simple recursion problem that can be solved in an O(2^n) time
edit adding pseudo-code 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 (i.e. from 1 0 1 1 0 display acd)
This will work with any collection. I modified @Sapp's answer a little
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 then if I have a set of strings I will use it as:
Here is some code I made. It constructs a list of all possible strings from an alphabet, of lengths 1 to maxLength: (in other words, we are calculating the powers 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;
}
}
something on the lines of an 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++;
}
?>
