如何組合出一個隨機生成的字符？

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個循環和簡單的交換實現了完整的組合！花了一段時間纔算正確的算法，但現在它已經被清理乾淨了，非常漂亮。
對於找到的每個組合，我們必須再次對這些字母進行排序並執行查找。

這給了我們所有可能的解決方案的字謎！