如何组合出一个随机生成的字符？

Question

我正在制作一个winforms应用程序，在这个应用程序中，它会生成7个字符长度的随机模式，比如2Velels-5consonants，3Vowels-4Consonants等等。之后它会生成特定于生成的模式的随机字母。

生成的字母后，我要的字母所有可能组合列出来生成信..并尝试检查产生的组合均存在于系统的字典..

- 样品输入 -

样式：3V-4C字母：AIOLMNC 个组合：AIO AOL OIL .... MAIL ....索赔....等等...

-Output-

几个词：OIL MAIL索赔.. 。等等......

这个程序是为文字游戏..我寻求帮助和任何建议，可能会帮助我解决我的问题。我想不出恰当的方式来启动算法和如何编写代码吧..

Answer 1

更新

该解决方案直接回答你的问题（“我怎样形成字符的所有组合”），但这是不是解决字形的非常有效的方法。我决定创建一个更好的解决方案来解决字谜，所以请看我的其他答案。

---

这听起来像一个有趣的谜题。
首先，这里是你如何创建你的“随机”输入：

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()可能是有意义的（尽管​​有一个跳过重复的算法，但更复杂）。

如您所述，最后一步是检查字典中的所有排列组合。

优化

该解决方案是相当简单的，并且可能会工作得很好，如果你的困惑仍然很小。然而，这绝对是一种“蛮力”的方法，随着难题变大，性能呈指数级下降！

Answer 2

我通常不会这样做，但我想出了一个更好的解决方案来解决您的问题，它值得自己回答！这个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); 
        } 
       } 
      } 
     } 
    } 

} 

这里的算法摘要：

的基本思想是，每一套字谜从派生同一组字母。
如果我们对字母进行排序，我们可以将多组字形组合在一起。
我从Algorithm for grouping anagram words得到了这个想法。
例如，可以在“AEMNS”上键入一组字符（“NAMES”，“MANES”，“MEANS”）。
因此，一旦我们创建了我们的字典查找，解决这个咒语的过程非常简单快捷 - 只需对字谜的字母进行排序并执行查找即可。

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

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