C # Как манипулировать списком для построения слов из разных символов?

Question

Я пишу программу, которая берет несколько букв, строит из них слова и возвращает слова, которые имеют смысл, которые можно найти в банке слов (например, в словаре английского языка).

Сначала я начал с двухдля циклов, которые берут букву и добавляют к ней все остальные буквы в порядке возрастания: если я дам (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);
    }
}

Теперь я пытаюсь выяснить, как лучше всего получить все остальные комбинации этих букв.

• Имеет ли это больше для циклов, но с другими условиями в скобках условий?
• Создает ли новый список для каждой буквы и манипулирует каждым списком по отдельности, а затем объединяет их вместе?
• Это с помощью Linq?

Я пытаюсь использовать больше для циклов с различными условиями, но задаюсь вопросом, является ли это лучшим способом достижения моей цели.

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