查找列表的所有子集

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

**然後，如果我有一組字符串我將用它作爲：