排列字符串列表算法

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是一个奇妙的图书馆。