試圖通過遞歸更優雅地解決電話單

Question

我已經瀏覽了堆棧溢出，但一直未能得到任何工作。我很抱歉，如果我錯過了一個明顯的明顯的職位。

我有一個學校的問題，涉及到一個電話號碼，獲取所有可能的單詞組合，然後將其寫入文本文件。我做到了，爲我的任務得到了充分的信任。我能夠用七個嵌套循環做到這一點，但這不是很優雅，而且非常僵硬。我被吹走了，完全失望地發現教科書解決方案有七個嵌套循環。我的老師也沒有任何答案。

我已經嘗試了許多不同的方法，但我一直無法獲得它撥入英寸我確定了一個遞歸和殺戮點，但從來沒有能夠得到它的工作。我可以產生這些字母序列，但不知道應該有多少。我評論了我的嘗試，所以你可以看到我的失敗思維過程:)請看看，讓我知道你是否有任何想法。

public partial class TelephoneWorderizer : Form 
{ 
    protected Dictionary<int, IEnumerable<string>> KeyMappings = new Dictionary<int, IEnumerable<string>>(); 
    protected string[][] ActiveLettersGroups = null; 
    protected List<string> Words = new List<string>(); 
    protected List<string> RecursiveWords = new List<string>(); 
    protected int Iteration = 0; 

    public TelephoneWorderizer() 
    { 
     InitializeComponent(); 

     this.KeyMappings = this.GetKeyMappings(); 
    } 

    private void btnGetWords_Click(object sender, EventArgs e) 
    { 
     string textBoxContent = textBoxNumber.Text; 

     int[] digits = this.GetPhoneNumbers(textBoxContent); 

     List<string> words = this.GetWords(digits); 

     using (StreamWriter writer = new StreamWriter(@"E:\words.txt")) 
     { 
      foreach (var word in words) 
      { 
       writer.WriteLine(word); 
      } 
     } 

     textBoxNumber.Clear(); 
    } 

    private List<string> GetWords(int[] digits) 
    { 
     List<string[]> letterGroupings = new List<string[]>(); 

     //digits array of numbers 
     for (int i = 0, j = digits.Length; i < j; i++) 
     { 
      int digit = digits[i]; 

      //if the number has a letter group mapped to it 
      if (this.KeyMappings.ContainsKey(digit)) 
      { 
       // letters mapped to a given number 
       letterGroupings.Add(this.KeyMappings[digit].ToArray()); 
      } 
     } 

     this.WordMakerLoop(letterGroupings); 
     //this.WordMaker(letterGroupings); 

     return this.Words; 
     //return this.RecursiveWords; 
    } 

    //private void RecursionTest(string word, List<string[]> groups, int letterCtr, int groupCtr) 
    //{ 
    // string[] Group = groups[groupCtr]; 

    // word += Group[letterCtr]; 

    // letterCtr += 1; 

    // if (letterCtr < Group.Length - 1) 
    // { 
    //  letterCtr = 0; 
    //  groupCtr += 1; 

    //  // Hit bottom 
    //  if (groupCtr == groups.Count - 1) 
    //  { 
    //   groupCtr -= 1; 
    //  } 

    //  RecursionTest(word, groups, letterCtr, groupCtr); 
    // } 
    //} 

    private void WordMaker(List<string[]> letterCollections) 
    { 
     string newword = ""; 
     int numberLength = letterCollections.Count; 

     this.ActiveLettersGroups = letterCollections.ToArray(); 

     string[] letterGroup = this.ActiveLettersGroups[0]; 

     this.RecursiveGetWords(newword, 0, 0); 
    } 

    /// <summary> 
    /// 
    /// </summary> 
    /// <param name="word"></param> 
    /// <param name="groupIndex"></param> 
    /// <param name="letterIndex"></param> 
    private void RecursiveGetWords(string word, int groupIndex, int letterIndex) 
    { 

     /* 
     * 
     * 
     * 
     */ 


     var numActiveLetterGroups = this.ActiveLettersGroups.Length; 

     if (this.ActiveLettersGroups.Length > 0 && this.Iteration < numActiveLetterGroups) 
     { 
      if (groupIndex < numActiveLetterGroups) 
      { 
       var letters = this.ActiveLettersGroups[groupIndex]; // Picks the a letter group ex: A, B, C 

       if (letterIndex < letters.Length) 
       { 
        //var letter1 = letters.Select(x => 
        string letter = letters[letterIndex]; // Picks a letter from the group ex: A 

        word += letter; 

        this.RecursiveGetWords(word, groupIndex + 1, this.Iteration); 
       } 
       else 
       { 
        //this.RecursiveWords.Add(word); 
        //word = ""; 

        //this.RecursiveGetWords(word, 0, 1); 
       } 
      } 
      else 
      { 
       this.RecursiveWords.Add(word); 
       word = ""; 
       this.Iteration++; 

       this.RecursiveGetWords(word, 0, this.Iteration); 
      } 
     } 
    } 

    #region 
    private void WordMakerLoop(List<string[]> letterGroups) 
    { 
     string word = ""; 

     // array of string[] 
     var newGroup = letterGroups.ToArray(); 

     //grabs a letter group 
     for (int i = 0; i < newGroup.Length; i++) 
     { 
      var letterGroup1 = newGroup[i]; 

      //grabs a letter from group 1 
      for (int j = 0; j < letterGroup1.Length; j++) 
      { 
       string letter1 = letterGroup1[j]; 

       if (i + 1 < newGroup.Length) 
       { 
        var letterGroup2 = newGroup[i + 1]; 

        //grabs a letter from group 2 
        for (int k = 0; k < letterGroup2.Length; k++) 
        { 
         string letter2 = letterGroup2[k]; 

         if (i + 2 < newGroup.Length) 
         { 
          var letterGroup3 = newGroup[i + 2]; 

          //grabs a letter from group 3 
          for (int l = 0; l < letterGroup3.Length; l++) 
          { 
           string letter3 = letterGroup3[l]; 

           if (i + 3 < newGroup.Length) 
           { 
            var letterGroup4 = newGroup[i + 3]; 

            //grabs a letter from group 4 
            for (int m = 0; m < letterGroup4.Length; m++) 
            { 
             string letter4 = letterGroup4[m]; 

             if (i + 4 < newGroup.Length) 
             { 
              var letterGroup5 = newGroup[i + 4]; 

              //grabs a letter from group 5 
              for (int n = 0; n < letterGroup5.Length; n++) 
              { 
               string letter5 = letterGroup5[n]; 

               if (i + 5 < newGroup.Length) 
               { 
                var letterGroup6 = newGroup[i + 5]; 

                //grabs a letter from group 6 
                for (int o = 0; o < letterGroup6.Length; o++) 
                { 
                 string letter6 = letterGroup6[o]; 

                 if (i + 6 < newGroup.Length) 
                 { 
                  var letterGroup7 = newGroup[i + 6]; 

                  //grabs a letter from group 6 
                  for (int p = 0; p < letterGroup7.Length; p++) 
                  { 
                   string letter7 = letterGroup7[p]; 

                   word = letter1 + letter2 + letter3 + letter4 + letter5 + letter6 + letter7; 
                   this.Words.Add(word); 
                   word = ""; 
                  } 
                 } 
                } 
               } 
              } 
             } 
            } 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 

    // Sanitizes input text and converts the string into and arra of int 
    private int[] GetPhoneNumbers(string content) 
    { 
     int[] phoneNumbers = null; 

     string cleanString = this.SanitizeString(content); 

     int numbers; 

     if (Int32.TryParse(cleanString, out numbers)) 
     { 
      //phoneNumbers = this.GetIntArray(numbers).OfType<int>().ToList(); 
      phoneNumbers = this.GetIntArray(numbers); 
     } 

     return phoneNumbers; 
    } 

    // Removes potential unwanted characters from the phone number 
    private string SanitizeString(string content) 
    { 
     content = content.Replace("-", ""); 
     content = content.Replace("(", ""); 
     content = content.Replace(")", ""); 

     return content; 
    } 

    //breaks a number into an array of its individual digits 
    private int[] GetIntArray(int num) 
    { 
     List<int> listOfInts = new List<int>(); 

     while (num > 0) 
     { 
      listOfInts.Add(num % 10); 
      num = num/10; 
     } 

     listOfInts.Reverse(); 

     return listOfInts.ToArray(); 
    } 

    //gets the mappings for the numerical values 
    private Dictionary<int, IEnumerable<string>> GetKeyMappings() 
    { 
     List<string> alphabet = new List<string>() { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" }; 
     Dictionary<int, IEnumerable<string>> mappings = new Dictionary<int, IEnumerable<string>>(); 

     for (int i = 0; i < 10; i++) 
     { 
      string[] letters = null; 
      switch (i) 
      { 
       case 0: 
       case 1: 
        break; 
       case 2: 
       case 3: 
       case 4: 
       case 5: 
       case 6: 
       case 8: 
        letters = alphabet.Take(3).ToArray(); 
        mappings.Add(i, letters); 
        alphabet.RemoveRange(0, 3); 
        break; 
       case 7: 
       case 9: 
        letters = alphabet.Take(4).ToArray(); 
        mappings.Add(i, letters); 
        alphabet.RemoveRange(0, 4); 
        break; 
       default: 
        break; 
      } 
     } 

     return mappings; 
    } 
    #endregion 
} 

讓我強調，對於那些疑惑的人來說，學校的任務已經結束。我想更好，更高效地做到這一點。如果這有幫助，我可以在gitHub上發佈我的項目。

Answer 1

我現在懶得寫任何代碼，但你一定能夠通過遞歸而不是七個嵌套循環來做到這一點，事實上，你應該能夠設計一個方法，應該可以在任何任意長度的電話號碼。

的基本想法是，你會設計一個遞歸方法是這樣的：

void recurse(String phone, int index, StringBuilder sb) 
{ 
    // Get the number at position phone[index] 
    // Loop through the possible letters for that particular number (eg. A, B, C): 
     // Add the letter to the StringBuilder 
     // Call recurse(phone, index + 1, sb) 
     // Subtract last letter from the StringBuilder 
} 

每次遞歸你的下一個數字/字母位置的工作時間。

當然，如果遇到終止條件（sb length == phone length），那麼不用遞歸，而是將StringBuilder的當前值寫入文件並返回。

希望這會有所幫助。

編輯：到處去實際編寫一些代碼。這真是這個簡單，沒有LINQ要求：

class Program 
    { 
     static Dictionary<Char, String> DigitMap = new Dictionary<Char, String>() 
     { 
     {'0', "0"}, 
     {'1', "1"}, 
     {'2', "ABC"}, 
     {'3', "DEF"}, 
     {'4', "GHI"}, 
     {'5', "JKL"}, 
     {'6', "MNO"}, 
     {'7', "PQRS"}, 
     {'8', "TUV"}, 
     {'9', "WXYZ"} 
     }; 

     static void Main(string[] args) 
     { 
     String phone = Regex.Replace("867-5309", "[^0-9]", ""); 
     recurse(phone, 0, new StringBuilder()); 
     } 

     static void recurse(String phone, int index, StringBuilder sb) 
     { 
     // Terminating condition 
     if (index == phone.Length) 
     { 
      Console.WriteLine(sb.ToString()); 
      return; 
     } 

     // Get digit and letters string 
     Char digit = phone[index]; 
     String letters = DigitMap[digit]; 

     // Loop through all letter combinations for digit 
     foreach (Char c in letters) 
     { 
      sb.Append(c); 
      recurse(phone, index + 1, sb); 
      sb.Length -= 1; 
     } 
     } 
    } 
} 

在這段代碼（如果我做了一個簡單的控制檯應用程序），我只是寫話到控制檯，但你可以添加字符串數組或書寫他們改爲磁盤。

Answer 2

這裏的Javaish僞codeish遞歸函數：上面寫着C＃和它適應你的代碼後

void recWords(String number, int ind, String buf, Collection<String> result){ 
    if(ind==number.length()) { 
    result.add(buf); 
    } else { 
    for(char letter : lettersForNumber(number.charAt(ind)) { 
     recWords(number, ind+1, buf+letter, result); 
    } 
    } 
} 

而且excercises：從String

1. 變化buf到一個共享StringBuilder。
2. 然後將其包裝到類中，並且只傳遞ind中的其他值作爲類 成員變量。
3. 然後最後把遞歸轉換成循環（提示：3個嵌套循環，其中一個內部循環將有越來越多的迭代）。

注意有關非遞歸版本我想：這會比遞歸效率較低，但就是它的有趣和有價值的編碼作爲一個練習是，這將是breadth-first，而這個遞歸版本depth-first 。

Answer 3

我已經假設您可能想要將每個數字轉換爲自身以及所有常規字母映射，並將0映射到+。所以我做了這個字典來處理映射：

var map = new Dictionary<char, string>() 
{ 
    { '0', "+0"}, 
    { '1', "1" }, 
    { '2', "2ABC"}, 
    { '3', "3DEF"}, 
    { '4', "4GHI"}, 
    { '5', "5JKL"}, 
    { '6', "6MNO"}, 
    { '7', "7PQRS"}, 
    { '8', "8TUV"}, 
    { '9', "9WXYZ"}, 
}; 

我重排列功能則是這樣的：

Func<IEnumerable<char>, IEnumerable<IEnumerable<char>>> permutate = null; 
permutate = cs => 
{ 
    var result = Enumerable.Empty<IEnumerable<char>>(); 
    if (cs.Any()) 
    { 
     result = map[cs.First()].Select(c => new [] { c }); 
     if (cs.Skip(1).Any()) 
     { 
      result = 
       from xs in result 
       from ys in permutate(cs.Skip(1)) 
       select xs.Concat(ys); 
     } 
    } 
    return result; 
}; 

就是這樣。

您可以使用它像這樣：

var digits = "(08) 8234-5678" 
    .Where(x => char.IsDigit(x)); 

var results = 
    permutate(digits) 
     .Select(x => new string(x.ToArray())); 

結果是一個字符串，其中每個字符串是輸入數字的排列的列表。

如果您不想將數字映射到數字，只需將它們從原始字典定義中移出即可，但您必須保留數字1的單個字符才能使其工作。

讓我知道這是否適合你。

Answer 4

這裏有一個非遞歸解決方案，即

• 給定一個數字，計算它
• 給出一個單詞的第一個字，「增量」它來尋找下一個字

public static class TelephoneFinder 
{ 
    static char[] firstDigits = new char[] 
        { '0', '1', 'A', 'D', 'G', 'J', 'M', 'P', 'T', 'W' }; 
    public static string First(string number) 
    { 
     char[] firstWord = new char[number.Length]; 
     for (int i = 0; i < number.Length; i++) 
     { 
      var c = number.Substring(i, 1); 
      firstWord[i] = firstDigits[int.Parse(c)]; 
     } 
     return new String(firstWord); 
    } 

    static Dictionary<char, char> rollovers = new Dictionary<char, char> { 
     { '1', '0' }, { '2', '1' }, { 'D', 'A' }, { 'G', 'D' }, { 'J', 'G' }, 
     { 'M', 'J' }, { 'P', 'M' }, { 'T', 'P' }, { 'W', 'T' }, { '[', 'W' } }; 
    public static string Next(string current) 
    { 
     char[] chars = current.ToCharArray(); 
     for (int i = chars.Length - 1; i >= 0; i--) 
     { 
      // Increment current character 
      chars[i] = (char)((int)chars[i] + 1); 

      if (rollovers.ContainsKey(chars[i])) 
       // Roll current character over 
       // Will then continue on to next character 
       chars[i] = rollovers[chars[i]]; 
      else 
       // Finish loop with current string 
       return new String(chars); 
     } 
     // Rolled everything over - end of list of words 
     return null; 
    } 
} 

稱爲eg

string word = TelephoneFinder.First("867"); 
while (!String.IsNullOrEmpty(word)) 
{ 
    Console.WriteLine(word); 
    word = TelephoneFinder.Next(word); 
} 

它很可能使用了一些整理，但它是一個一般的非遞歸解決方案，可以進行修改，以類似「跨產品」的情況下工作。

Answer 5

我很抱歉大家。這是我的第一個堆棧溢出帖子，當我的問題發佈回答時，我正在等待一封電子郵件，但從未收到過。我只是覺得我的問題被吞沒了堆棧溢出的深淵。

我與之合作的一組開發人員在約5行中找到了這一個。目前我似乎無法找到解決方案，但我認爲它與Enigmativity發佈的內容非常接近。我很積極，我們用排列組合。我會尋找我們使用的解決方案。感謝大家。