如何从随机生成的字符中形成组合

我通常不会这么做，但我为您的问题找到了一个更好的解决方案，它值得自己的答案！这个AnagramSolver解决方案比我的另一个答案优化得多，因为它不会创建单词的每一个排列，字典查找也非常优化。试试看：

用法示例：

string[] dictionary = ReadDictionary(...);
var solver = new AnagramSolver(dictionary);
int minimumLength = 1;
IEnumerable<string> results = solver.SolveAnagram("AEMNS", minimumLength);
// Output the results:
foreach (var result in results)
{
    Console.WriteLine(result);
}
// Output example: 
// "NAMES", "MANES", "MEANS", "AMEN", "MANE", "MEAN", "NAME", "MAN", "MAE", "AM", "NA", "AN", "MA", "A",

代码：

public class AnagramSolver
{
    public AnagramSolver(IEnumerable<string> dictionary)
    {
        // Create our lookup by keying on the sorted letters:
        this.dictionary = dictionary.ToLookup<string, string>(SortLetters);
    }
    private ILookup<string, string> dictionary;
    public IEnumerable<string> SolveAnagram(string anagram, int minimumLength)
    {
        return CreateCombinations(anagram, minimumLength)
            // Sort the letters:
            .Select<string, string>(SortLetters)
            // Make sure we don't have duplicates:
            .Distinct()
            // Find all words that can be made from these letters:
            .SelectMany(combo => dictionary[combo])
            ;
    }
    private static string SortLetters(string letters)
    {
        char[] chars = letters.ToCharArray();
        Array.Sort(chars);
        return new string(chars);
    }
    /// <summary> Creates all possible combinations of all lengths from the anagram. </summary>
    private static IEnumerable<string> CreateCombinations(string anagram, int minimumLength)
    {
        var letters = anagram.ToCharArray();
        // Create combinations of every length:
        for (int length = letters.Length; length >= minimumLength; length--)
        {
            yield return new string(letters, 0, length);
            // Swap characters to form every combination:
            for (int a = 0; a < length; a++)
            {
                for (int b = length; b < letters.Length; b++)
                {
                    // Swap a <> b if necessary:
                    char temp = letters[a];
                    if (temp != letters[b]) // reduces duplication
                    {
                        letters[a] = letters[b];
                        letters[b] = temp;
                        yield return new string(letters, 0, length);
                    }
                }
            }
        }
    }
}

以下是算法摘要：

其基本思想是，每一组变位词都源自同一组字母
如果我们对字母进行排序，我们就可以把一组变位词组合在一起
我从组合变位词的算法中得到了这个想法
例如，可以在"AEMNS"上键入一组字谜("NAMES"、"MANES"、"MEANS"(
因此，一旦我们创建了字典查找，就可以非常容易和快速地求解变位词——只需对变位词的字母进行排序并执行查找。

下一个挑战是找到所有"较小"的字谜——例如，找到"NAME"、"SANE"、"MAN"、"AN"、"A"等。
这可以通过查找变位符的所有组合来完成
组合比排列更容易找到不需要递归。我用3个循环和一个简单的交换实现了完整的组合！花了一段时间才把算法弄对，但现在它已经清理干净了，非常漂亮
对于找到的每个组合，我们必须再次对字母进行排序并执行查找。

这为我们提供了所有可能的字谜解决方案！

更新

这个解决方案直接回答了你的问题("我如何形成所有字符组合"(，但这不是一个非常有效的解决变位词的方法。我决定创建一个更好的解决方案来解决字谜，所以请看我的另一个答案。

这听起来像一个有趣的谜题
首先，以下是如何创建您的"；"随机"；输入：

Random rng = new Random();
const string vowels = "AEIOU";
const string consonants = "BCDFGHJKLMNPQRSTVWXYZ";
string CreatePuzzle(int vowelCount, int consonantCount){
    
    var result = new StringBuilder(vowelCount + consonantCount);
    for (int i = 0; i < vowelCount; i++) {
        result.Append(vowels[rng.Next(5)]);
    }
    for (int i = 0; i < consonantCount; i++) {
        result.Append(consonants[rng.Next(21)]);
    }
    
    return result.ToString();
}

然后你需要创建这些字母的所有排列。这对于递归来说是一项伟大的工作。以下代码是我在http://www.cut-the-knot.org/do_you_know/AllPerm.shtml.另一个有用的资源是http://www.codeproject.com/KB/recipes/Combinatorics.aspx

/// <summary>
/// Returns all permutations of the puzzle.
/// Uses "Heap's Algorithm" found at http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
/// </summary>
IEnumerable<string> CreatePermutations(string puzzle) {
    // It is easier to manipulate an array; start off the recursion:
    return CreatePermutations(puzzle.ToCharArray(), puzzle.Length);
}
IEnumerable<string> CreatePermutations(char[] puzzle, int n) {
    if (n == 0) {
        // Convert the char array to a string and return it:
        yield return new string(puzzle);
    } else {
        // Return the sub-string:
        if (n < puzzle.Length) {
            yield return new string(puzzle, n, puzzle.Length - n);
        }
        // Create all permutations:
        for (int i = 0; i < n; i++) {
            // Use recursion, and pass-through the values:
            foreach (string perm in CreatePermutations(puzzle, n-1)) {
                yield return perm;
            }
            // Create each permutation by swapping characters: (Heap's Algorithm)
            int swap = (n % 2 == 1) ? 0 : i;
            char temp = puzzle[n-1];
            puzzle[n-1] = puzzle[swap];
            puzzle[swap] = temp;
        }
    }
}

请注意，该算法不检查重复项，因此类似"；AAA"；仍将导致6个排列。因此，对结果调用.Distinct()可能是有意义的(尽管CodeProject文章有一个跳过重复的算法，但更复杂(。

正如你所说，最后一步是对照你的字典检查所有的排列。

优化

这个解决方案相当简单，如果你的谜题仍然很小，可能会非常有效。然而，它绝对是一个"；暴力"；这种方法，随着谜题越来越大，性能呈指数级下降！