字符串列表的置换算法

本文关键字：算法 列表 字符串 | 更新日期: 2023-09-27 18:21:39

我需要帮助理解如何编写置换算法。（如果这是偶数排列，它们必须按顺序排列并使用相同的值）。

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个排列。

private List<string> permute(List<string> values, int maxPermutation)
{
     //alittle help on starting it would be great :)
}

我看了看，但他没有遵守秩序。

字符串列表的置换算法

这很简单：您有三个位置，可以在其中放置逗号，也可以不放置任何内容。有八种组合对应2^3二进制数。

对于从0到7（包括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);     
}

您可以采用递归方法：取第一个字母，从第二个字母开始构建所有可能的组合（这是递归…），并将第一个字母作为每个字母的前缀。然后将前两个字母放在一起，从第三个字母开始递归构建所有组合。等等

至于你的额外要求：如果你想排除所有包含X字母字符串的"组合"，在构造第一个字符串时只需跳过这个数字。

上面的二进制方法是正确的，这实际上是一个分区问题（但不是"分区问题"），而不是排列问题。

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

注意，因为分区的数量增长速度比指数（e^e^n）快，所以对于大型字符串来说，速度会非常慢。

尝试以下代码。我还没有测试过，但我想这正是你想要的。

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

如果你需要生成组合（或排列或变体），那么组合数学是一个很棒的库。

相关文章：