再帰を使って電話の言葉をよりエレガントに解決しようとしています

Question

私はスタックオーバーフローを調べましたが、何もできませんでした。私は大変明白な投稿を逃した場合は謝罪します。

私は学校の問題を抱えていました。電話番号を取って単語の組み合わせをすべて取り、それをテキストファイルに書き込んでいました。私はそれをして、私の任務に全面的な信用を得ました。私は7つのネストされたループでこれを行うことができましたが、それは非常に優雅ではなく、非常に堅いです。私は吹き飛ばされ、教科書のソリューションが7つのネストされたループであることを完全に失望させました。私のインストラクターにも答えはありませんでした。

私は多くの異なるアプローチを試みましたが、私はそれをダイヤルインできませんでした。私は再帰とキルポイントを特定しましたが、それを動作させることはできませんでした。私は文字列を生成することができますが、どれくらいの数の文字列が存在するはずはありません。私はあなたが私の失敗した思考プロセスを見ることができるように私の試みをコメントアウトしました:)あなたが何か考えているかどうかを見て、私に知らせてください。

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

私は現時点ではコードを書くのが面倒ですが、7つのネストされたループではなく、再帰によってこれを行うことができるはずです。実際には、どんなコードでも動作するメソッドを設計できるはずです。任意の長さの電話番号。

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の現在の値をfileに書き込んで返してください。

これが役に立ちます。

編集：実際にいくつかのコードを書いています。それは本当にこのシンプルだし、何の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; 
     } 
     } 
    } 
} 

をこのコードでは（私は、単純なコンソールアプリケーションを作っている）私はちょうどコンソールに言葉を書いていますが、配列や書き込みに文字列を追加することができ代わりにディスクに書き込んでください。 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); 
    } 
    } 
} 

さらにエクササイズ：ここ

Answer 2

はJavaish擬似codeish再帰関数です

1. 変更bufは1つにStringからStringBuilderを共有しました。
2. これをクラスにラップし、再帰でindのみを渡し、他のメンバーをクラス メンバ変数として渡します。
3. 最後に、ループを繰り返します（ヒント：3つのネストされたループ、内部ループの1つに反復回数が増えます）。この再帰バージョンはdepth-firstている間、それは再帰よりも効率になりますが、何が面白いと運動があるとして、コーディングの価値になり、それがbreadth-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"}, 
}; 

マイpermutate機能は、その後、次のようになります。

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

たとえば

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

は、それはおそらく、いくつかの片付け使用することができますが、それは同様の「外積」の状況で動作するように変更することができ、一般的な非再帰的なソリューションです。

Answer 5

ごめんなさい。これは私の最初のスタックオーバーフローポストでした、私は答えが私の質問に投稿されたが、決して1つを持っていないときに電子メールを期待していた。私はちょうど私の質問がスタックのオーバーフローの深みに飲み込まれたと考えました。

開発者のグループは、私は約5行で考え出したものを持っています。私は現時点で解決策を見つけることができないようですが、Enigmativityが投稿したものに非常に近いと思います。私は順列を使ったことは肯定的です。私が使用したソリューションを探します。みんな、ありがとう。