排列字符串列表算法

Question

我需要幫助瞭解如何編寫排列算法。 （如果這是偶數排列，則必須按順序並使用相同的值）。

List<string> str = new List<string>{"a", "b", "c", "d"}; 

如何我能得到這個列表中提供每個排列的名單？例如。

1. a, b, c, d
2. ab, c, d
3. ab, cd
4. abc, d
5. abcd
6. a, bc, d
7. a, bcd
8. a, b, cd

出於某種原因，我無法找到下手的模式。當連接字符串的計數類似於X字符時，我還希望能夠忽略排列。所以如果X是4，在那個列表中，數字5將不存在，並且將有7個排列。我看了看this，但他不保留訂單。

Answer 1

這很簡單：你有三個位置，你可以放一個逗號或不放任何東西。有八個組合對應於2^3個二進制數。

對於從0到7（含）的每個數字，產生一個二進制表示。在二進制表示有1的每個位置放一個逗號;不要把逗號放在零的地方。

for (int m = 0 ; m != 8 ; m++) { 
    string s = "a"; 
    if ((m & 1) != 0) s += ","; 
    s += "b"; 
    if ((m & 2) != 0) s += ","; 
    s += "c"; 
    if ((m & 4) != 0) s += ","; 
    s += "d"; 
    Console.WriteLine(s);  
} 

Answer 2

您可以採用遞歸方法：取第一個字母，從第二個字母開始（這是遞歸...），並將第一個字母添加到每個字母。然後將前兩個字母組合在一起，遞歸地構建從第三個開始的所有組合。等等......

至於你的附加要求：如果你想排除包含字符串的所有「組合」，其中包含字母爲X的字母，只需在構造第一個字符串時跳過此數字即可。

Answer 3

上面的二進制方法是正確的，這其實是一個劃分問題（而不是「分割問題」），而不是一個置換問題。

http://en.wikipedia.org/wiki/Partition_of_a_set

當心，因爲分區數量的增加呈指數比速度（E^E^N），所以這將是大串很慢。

Answer 4

請嘗試以下代碼。我沒有測試過，但我認爲這是你正在尋找的。

List<string> str = new List<string>{ "a", "h", "q", "z", "b", "d" }; 
List<List<string>> combinations = combine(str.OrderBy(s=>s).ToList()); 

List<List<string>> combine(List<string> items) 
{ 
    List<List<string>> all = new List<List<string>>(); 

    // For each index item in the items array 
    for(int i = 0; i < items.Length; i++) 
    { 
     // Create a new list of string 
     List<string> newEntry = new List<string>(); 
     // Take first i items 
     newEntry.AddRange(items.Take(i)); 
     // Concatenate the remaining items 
     newEntry.Add(String.concat(items.Skip(i))); 
     // Add these items to the main list 
     all.Add(newEntry); 

     // If this is not the last string in the list 
     if(i + 1 < items.Length) 
     { 
      // Process sub-strings 
      all.AddRange(combine(items.Skip(i + 1).ToList())); 
     } 
    } 
    return all; 
} 

如果你需要生成組合（或置換或變化），然後Combinatorics是一個奇妙的圖書館。