Найти все подмножества списка

Question

У меня есть список, и мне нужно вывести каждое подмножество списка

например a b c d e

будет выводить до

 a
 b
 c  
 d 
 e 
 ab  
 ac  
 ad 
 ae

 abc
 abd 
 abe
 bcd
 bce
 ....
 abcde

Я считаю, что правильный термин - комбинация, ни один элемент не должен дублироваться в одной строке

Я собирался попробовать это с помощью серии циклов, но я даже не уверен, что мы должны начинать

есть предложения?

Answer 1

Если вам нужны только комбинации элементов в вашем исходном списке, вы можете преобразовать проблему в следующее: у вас есть битовый массив размера N, и вы хотите найти все возможные варианты для элементов массива. Например, если ваш первоначальный список

a b c d e

тогда ваш массив может быть

0 1 0 0 0

, что приводит к выводу

b

или массив может быть

1 0 1 1 0

, который возвращает

acd

это простая проблема рекурсии, которая может быть решена за O(2^n) время

edit добавление псевдокода для алгоритма рекурсии:

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)

Answer 2

Это сгенерирует набор, который вы хотите, но в другом порядке (в конце я сортирую по алфавиту, вам также нужно отсортировать по длине).

Вы получите:

а аб азбука ABCD ABCDE ABCE ... d де е

Итак, каждое возможное подмножество (кроме пустой строки) при сохранении порядка исходного списка.

Идея состоит в том, чтобы добавить каждый элемент в растущий список. С каждым новым элементом сначала добавьте его, а затем добавьте его ко всем существующим элементам.

Итак, начните с «а».

Перейти к «б». Добавьте это в список. Теперь у нас есть {'a', 'b'}.

Добавьте его к существующим элементам, чтобы у нас было 'ab'. Теперь у нас есть {'a', 'b', 'ab'}.

Затем 'c' и добавьте его к существующим элементам, чтобы получить 'ac', 'bc', 'abc': {'a', 'b', 'ab', 'c', 'ac', ' bc ', abc'}. И так до тех пор, пока мы не закончим.

        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 3

Это будет работать с любой коллекцией.Я немного изменил @ Sapp's ответ

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

** И тогда, если у меня есть набор строк, я буду использовать его как:

Answer 4

что-то в строках расширенного цикла while:

<?

$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

Вот код, который я сделал. Он создает список всех возможных строк из алфавита длиной от 1 до maxLength: (другими словами, мы рассчитываем степень алфавита)

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