C# 如何操作一个列表来从不同的字符构建单词？

Question

我正在编写一个程序，它接受几个字母，从中构建单词并返回可以在词库(如英语词典)中找到的有意义的词。

首先，我从两个 for 循环开始，这两个循环接受一个字母，然后按升序将所有其他字母添加到该字母中:如果我给出 (A, D, B, H)，输出将是:AD、ADB、ADBH、DA , DAB, DABH 等

var scrambledWords = new List<string>();

for (int i = 0; i < buildingMaterial.Count; i++)
{
    firstBuildUp = buildingMaterial[i];

    for (int j = 1; j < buildingMaterial.Count; j++)
    {
        if (buildingMaterial[j] == buildingMaterial[i])
            continue;

        firstBuildUp += buildingMaterial[j];
        scrambledWords.Add(firstBuildUp);
    }
}

现在我正试图弄清楚什么是获得这些字母的所有其他组合的最佳方法。

• 是否有更多的 for 循环但条件括号中的条件不同？
• 是否为每个字母创建新列表并单独操作每个列表，然后将它们组合在一起？
• 是使用 Linq 吗？

我正在尝试在不同条件下使用更多 for 循环，但想知道这是否是实现我目标的最佳方式。

Answer 1

您正在寻找的是一个集合的所有可能子集，或者更确切地说，PowerSet一套。你可以使用扩展方法来查找幂集:

public static class ListExtensions
{
    public static List<List<T>> PowerSet<T>(this List<T> set)
    {
        var n = set.Count;

        var powerSetCount = 1 << n;

        var result = new List<List<T>>();

        for (var setMask = 0; setMask < powerSetCount; setMask++)
        {
            var subset = new List<T>();
            for (var i = 0; i < n; i++)
            {
                if ((setMask & (1 << i)) > 0)
                {
                    subset.Add(set[i]);
                }
            }

            result.Add(subset);
        }

        return result;
    }
}

然后像这样使用它

static class Program
{
    static void Main()
    {
        var powerSet = "abc".ToList().PowerSet();

        foreach (var set in powerSet)
        {
            // set will be a list of chars, which is equivalent to a string
            Console.WriteLine($"{new string(set.ToArray())}");
        }

        Console.ReadLine();
    }
}

输出将是:

a
b
ab
c
ac
bc
abc

请注意，空集也是 PowerSet

的一部分

编辑:

字符串扩展版本:

public static class StringExtensions
{
    public static List<string> PowerSet(this string str)
    {
        var n = str.Length;

        var powerSetCount = 1 << n;

        var result = new List<string>();

        for (var setMask = 0; setMask < powerSetCount; setMask++)
        {
            var subset = new StringBuilder();
            for (var i = 0; i < n; i++)
            {
                if ((setMask & (1 << i)) > 0)
                {
                    subset.Append(str[i]);
                }
            }

            result.Add(subset.ToString());
        }

        return result;
    }
}