查找列表的所有子集

Question

我有一个名单，我需要输出ABCDE

将输出到

a 
b 
c 
d 
e 
ab 
ac 
ad 
ae 

abc 
abd 
abe 
bcd 
bce 
.... 
abcde 

我认为正确的说法是列表

例如每个子集组合没有元素应该在同一行上复制

我打算尝试这一系列的循环，但我甚至不知道要开始

有什么建议吗？

Answer 1

这将生成你想要的集合，但是以不同的顺序（我最后按字母顺序排序，你也想按照长度排序）。

最终你会用：

一个 AB ABC ABCD ABCDE ABCE ... d 德 Ë

所以，每一个可能的子集（除了空字符串），同时保持原始列表的顺序。

这个想法是将每个元素添加到不断增加的列表中。使用每个新元素，首先添加它，然后将其添加到所有现有元素。

所以，从'a'开始。

转到'b'。将它添加到列表中。我们现在有{'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 2

这是我制作的一些代码。它构建从字母的所有可能的字符串列表，长度1至最大长度：（换句话说，我们计算的是字母的权力）

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

Answer 3

东西上的一个延伸，而环行：

<? 

$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 4

如果你需要的是在你原来的列表中元素的组合，您可以将问题划分为以下几点：你有大小为N的位阵列，你想找到的元素所有可能的选择的阵列。例如，如果原始列表是

a b c d e

那么你的阵列可以是

0 1 0 0 0

这导致

b

的输出或所述阵列可以be

1 0 1 1 0

返回

acd

这是一个简单的递归问题，即可以在O(2^n)时间

编辑来解决添加伪代码递归算法：

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 5

这将适用于任何集合。我修改@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; 
    } 

**然后，如果我有一组字符串我将用它作为：