将字符串拆分并重新排列为所有可能的组合

Question

我希望将一个字符串拆分并重新排列成所有可能的组合。

假设有一个字符串：ABCDEF

我想要将其拆分并输出所有可能的组合。

Combination(6,6) = 1

ABCDEF

Combination(6,5) = 6

BCDEF
ACDEF
ABDEF
ABCEF
ABCDF
ABCDE

组合数(6,4) = 15

BCDE
ACDE
ABDE
ABCE
....
....
....
etc.

组合（6，3）= 20

BCD
ACD
...
etc.

Combination(6,2) = 15
BC
AB
等。

但是输出还必须按字母顺序排列。

我该怎么做？

谢谢！任何帮助都将不胜感激！

- Tony Wu

---

暴力破解算法...不好。 - Nahydrin

作业？你目前做了什么？ - user47589

请参见：https://dev59.com/1nNA5IYBdhLWcg3wWsUA - Anthony Pegram

我正在为我的软件专业项目制作一个类似于Scrabble的游戏。我可以在字典中搜索单词。例如，搜索“ABDE”，我将得到BEAD、BADE、ABED。然而，我想输入一个6个字母的单词，并获得其中所有的组合。 - Tony Wu

我曾经遇到过类似的问题，也许你可以尝试将字典放入一个不考虑字符顺序的格式中（例如按字母顺序组织每个单词中的字母，然后在每个唯一字母后面加上字母计数）。然后你只需要以相同的方式格式化搜索即可。 - Jess

Answer 1

你可以从Knuth的第4卷Fascicle 3中获取算法（实际上有几个），但是你需要将其从他的数学符号转换为C#。 更新：我认为更有用的是Fascicle 2（生成排列）。您可以免费下载它http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz，但您需要gunzip和PostScript预览器才能阅读它。生成字符串“ABCDE”的子集很容易。将其转换为数组{'A'，'B'，'C'，'D'，'E'}，在0到2^N-1之间运行for循环，其中N是数组长度，并将每个值视为元素掩码。因此，00001、00010、00011等给出“A”、“B”、“AB”... 生成每个子集的所有排列是困难的部分，因此您将获得“ABC”，“BAC”，“CAB”等。暴力算法（如其他答案中的算法）可以工作，但如果字符串很长，则会变得非常慢。 Knuth有一些快速算法，其中一些将按字母顺序生成排列，如果原始字符串首先排序。

- gatkin

---

Scrabble是排列而不是组合的一种案例。结果总数是e*n!而不是建议中的2^n-1。朴素解决方案对于问题规模（7个字母）非常直接和易处理，并且有一个好处，就是可以按字母顺序返回结果，这正是OP所要求的。 - gordy

@Gordy：OP在他的问题之后的评论中解释道，他有一个通过排序的字母序列索引的字典，因此可以查找ABDE并获得BEAD、BADE和ABED列表。鉴于此，他实际上不需要排列任何东西（当我回答问题时我没有意识到这一点），所以他没有n！问题。他显然卡在了找出可用字母的子集，以便组成较短的单词。 - gatkin

@Gordy：我承认我没有注意到OP指定了最大输入字符串长度。你是对的，这会有很大的影响。 - gatkin

Answer 2

嗯，为了进一步说明我的评论，我解决这个问题的方法是将字符串转换为一个不考虑字母顺序的哈希表。该哈希表通过获取每个唯一字母，然后是“:”，最后是该字母出现次数构成。

所以 test = e:1,s:1,t:2

然后，如果有人寻找单词tset，它将生成相同的哈希表（e:1,s:1,t:2），那么你就找到了一组匹配。

我刚刚运行了一个单词列表（大约有2000万个单词），为每个单词生成了一个哈希表，并将其放入mysql表中，我可以在几秒钟内找到一个单词的所有排列（它们本身也是单词，即ered将返回deer和reed）。

- Jess

Answer 3

您可以通过递增计数器并将计数器值转换为基于输入字母数的n进制来生成每个排列。丢弃任何包含重复字母的值，剩余的即为按字母顺序排序的可能Scrabble单词。

您将不得不计数到(n^(n-1))*(n+1)才能获取e * n! 可能的Scrabble单词。

char[] Letters = new char[] { 'A', 'B', 'C', 'D', 'E', 'F' };

// calculate e*n! (int)Math.Floor(Math.E * Math.Factorial(Letters.Length))
int x = 0;
for (int i = 1; i <= Letters.Length; i++)
    x = (x + 1) * i;

for (int i = 1; x > 0; i++)
{
    string Word = BaseX(i, Letters.Length, Letters);
    if (NoRepeat(Word))
    {
        Console.WriteLine(Word);
        x--;
    }
}

BaseX返回给定基数和指定符号的值的字符串表示形式：

string BaseX(int Value, int Base, char[] Symbols)
{
    StringBuilder s = new StringBuilder();

    while (Value > Base)
    {
        s.Insert(0, Symbols[Value % Base]);
        Value /= Base;
    }

    s.Insert(0, Symbols[Value - 1]);
    return s.ToString();
}

NoRepeat函数会在任何字母重复出现时返回false：

bool NoRepeat(string s)
{
    bool[] Test = new bool[256];

    foreach (char c in s)
        if (Test[(byte)c])
            return false;
        else
            Test[(byte)c] = true;

    return true;
}

- gordy

Answer 4

1. 将字符串按字母顺序排序，例如 ABCDEF（这是您的示例）
2. 准备一个索引和字符之间的映射

map[0] = 'A'; map[1] = 'B'; ... map[5] = 'F'

3. 现在你的工作变得更简单了：找到所有后面的数字比前面的数字大的数字组合

Combination(6,3):

for (int i = 0; i < 6 - 2; i++)
    for (int j = i + 1; j < 6 - 1; j++)
        for (int k = j + 1; k < 6; k++)
        {
            string strComb = map[i] + map[j] + map[k];
        }

这只是一个想法，您可以按照自己的方式进行改进。

如果您需要更多详细信息，请与我联系！

- longbkit

Answer 5

你可以使用这个：

static List<string> list = new List<string>();
static string letters = "bcdehijkmnopqrstuvwxyz";
static void Combine(string combinatory)
{
    if(combinatory.Length < letters.Length)
    {
        Parallel.ForEach(letters, l =>
        {
            if (!combinatory.Contains(l)) Combine(combinatory + l);
        }); 
    } else
    {
        list.Add(combinatory);
        Console.WriteLine(combinatory);
    }
}

它将添加到列表中所有可能的组合。

然后，您可以使用Sort()方法对列表进行排序。

- TheMineWay