如何实现从n组5字符数组生成所有可能排列组合单词？

需求说明 #

• 给定n个字符数组，每个数组固定包含5个字符
• 需要生成所有长度为2到n的字符序列：
  • 对于每个长度k（2 ≤ k ≤ n），从n个数组中选取k个不同的数组，对这k个数组的顺序做全排列，每个排列的每个位置从对应数组中取一个字符，生成所有可能的字符串（时间复杂度对应O(5^k)，k为当前序列长度）
• 从所有生成的序列中筛选出有效的英文单词

示例（n=4） #

当n=4时，4组字符数组如下：

N = 4

char[] characters1 = new char[5] { 'A', 'B', 'C', 'D', 'E' };
char[] characters2 = new char[5] { 'F', 'G', 'H', 'I', 'J' };
char[] characters3 = new char[5] { 'K', 'L', 'M', 'N', 'O' };
char[] characters4 = new char[5] { 'P', 'Q', 'R', 'S', 'T' };

需要生成的序列示例：

• 2字符：AF、AG、FB、GA 等
• 3字符：AFK、BFK、FBK 等
• 4字符：AFKP 等
  最终从这些序列中筛选出有效单词。

现有代码框架 #

char[] characters1 = new char[5] { 'A', 'B', 'C', 'D', 'E' };
char[] characters2 = new char[5] { 'F', 'G', 'H', 'I', 'J' };
char[] characters3 = new char[5] { 'K', 'L', 'M', 'N', 'O' };
char[] characters4 = new char[5] { 'P', 'Q', 'R', 'S', 'T' };

private List<string> FindWords(List<char[]> characters)
{
    // length of arrays are always 5

}
static void permute(String s, String answer)
{
    if (s.Length == 0)
    {
        Console.Write(answer + " ");
        return;
    }
    for (int i = 0; i < s.Length; i++)
    {
        char ch = s[i];
        String left_substr = s.Substring(0, i);
        String right_substr = s.Substring(i + 1);
        String rest = left_substr + right_substr;
        permute(rest, answer + ch);
    }
}

完善后的FindWords实现 #

实现思路 #

1. 准备有效单词集合（可替换为实际字典或词库）
2. 遍历所有目标长度k（从2到数组总数n）
3. 生成所有k个不同数组索引的组合，避免重复选取同一数组
4. 对每个索引组合生成全排列，覆盖数组的所有顺序可能
5. 针对每个索引排列，生成所有可能的字符组合（每个数组取一个字符，共5^k种）
6. 筛选出符合条件的有效单词，加入结果列表并去重

完整代码 #

using System;
using System.Collections.Generic;
using System.Linq;

class WordFinder
{
    char[] characters1 = new char[5] { 'A', 'B', 'C', 'D', 'E' };
    char[] characters2 = new char[5] { 'F', 'G', 'H', 'I', 'J' };
    char[] characters3 = new char[5] { 'K', 'L', 'M', 'N', 'O' };
    char[] characters4 = new char[5] { 'P', 'Q', 'R', 'S', 'T' };

    // 示例有效单词集合，实际使用可替换为外部字典或词库查询
    private HashSet<string> validWords = new HashSet<string> { "AF", "AG", "FB", "GA", "AFK", "BFK", "FBK", "AFKP" };

    private List<string> FindWords(List<char[]> characters)
    {
        List<string> result = new List<string>();
        int n = characters.Count;

        // 遍历所有目标长度k（2到n）
        for (int k = 2; k <= n; k++)
        {
            // 生成所有k个不同索引的组合
            var indexCombinations = GetCombinations(Enumerable.Range(0, n).ToList(), k);
            
            foreach (var combo in indexCombinations)
            {
                // 将组合转为字符串，用于生成全排列
                string indicesStr = string.Join("", combo);
                List<string> permutations = new List<string>();
                GeneratePermutations(indicesStr, "", permutations);
                
                foreach (var perm in permutations)
                {
                    // 生成该索引排列对应的所有字符组合
                    List<string> currentStrings = new List<string> { "" };
                    foreach (char c in perm)
                    {
                        int arrIndex = int.Parse(c.ToString());
                        char[] chars = characters[arrIndex];
                        List<string> temp = new List<string>();
                        foreach (string s in currentStrings)
                        {
                            foreach (char ch in chars)
                            {
                                temp.Add(s + ch);
                            }
                        }
                        currentStrings = temp;
                    }
                    
                    // 筛选有效单词并去重
                    foreach (string str in currentStrings)
                    {
                        if (validWords.Contains(str) && !result.Contains(str))
                        {
                            result.Add(str);
                        }
                    }
                }
            }
        }

        return result;
    }

    // 生成组合：从列表中选count个元素的所有组合
    private List<List<int>> GetCombinations(List<int> list, int count)
    {
        List<List<int>> result = new List<List<int>>();
        if (count == 0)
        {
            result.Add(new List<int>());
            return result;
        }
        if (list.Count == count)
        {
            result.Add(new List<int>(list));
            return result;
        }
        // 包含第一个元素的组合
        foreach (var combo in GetCombinations(list.Skip(1).ToList(), count - 1))
        {
            combo.Insert(0, list[0]);
            result.Add(combo);
        }
        // 不包含第一个元素的组合
        result.AddRange(GetCombinations(list.Skip(1).ToList(), count));
        return result;
    }

    // 生成字符串的全排列，存入结果列表
    private void GeneratePermutations(string s, string answer, List<string> result)
    {
        if (s.Length == 0)
        {
            result.Add(answer);
            return;
        }
        for (int i = 0; i < s.Length; i++)
        {
            char ch = s[i];
            string leftSubstr = s.Substring(0, i);
            string rightSubstr = s.Substring(i + 1);
            string rest = leftSubstr + rightSubstr;
            GeneratePermutations(rest, answer + ch, result);
        }
    }

    // 测试入口
    static void Main(string[] args)
    {
        WordFinder finder = new WordFinder();
        List<char[]> charsList = new List<char[]>
        {
            finder.characters1, finder.characters2, finder.characters3, finder.characters4
        };
        List<string> words = finder.FindWords(charsList);
        Console.WriteLine("找到的有效单词：");
        foreach (string word in words)
        {
            Console.Write(word + " ");
        }
    }
}

说明 #

• GetCombinations方法确保只选取不同的数组，避免重复组合
• GeneratePermutations基于原permute函数修改，将排列结果存入列表而非直接打印
• validWords为示例词库，实际项目中可替换为读取外部字典文件、使用.NET拼写检查类或调用词库API
• 结果列表自动去重，避免同一有效单词被多次添加

内容的提问来源于stack exchange，提问作者Amirhossein