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?

回答1:

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

回答2:

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)

回答3:

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

回答4:

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++;
}



?>

回答5:

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: