Versuchen, Telefonwort eleganter mit Rekursion

Question

zu lösen Ich habe Stapelüberlauf geschaut, aber bin nicht im Stande gewesen, etwas zum Arbeiten zu erhalten. Ich entschuldige mich, wenn ich einen offensichtlichen Post verpasst habe.

Ich hatte ein Schulproblem, bei dem ich eine Telefonnummer nahm, alle möglichen Wortkombinationen bekam und sie dann in eine Textdatei schrieb. Ich tat das und bekam volle Anerkennung für meine Aufgabe. Ich konnte dies mit sieben verschachtelten Schleifen tun, aber das ist nicht sehr elegant und ist sehr starr. Ich war hin und weg und völlig enttäuscht, dass die Lehrbuchlösung aus sieben verschachtelten Schleifen bestand. Mein Lehrer hatte auch keine Antworten.

Ich habe viele verschiedene Ansätze ausprobiert, aber ich konnte es nicht einwählen. Ich identifizierte eine Rekursion und den Tötungspunkt, konnte es aber nie zum Laufen bringen. Ich kann die Buchstabensequenzen erzeugen, aber nicht annähernd, wie viele es sein sollten. Ich habe meine Versuche auskommentiert, damit Sie meine gescheiterten Denkprozesse sehen können. Bitte werfen Sie einen Blick und lassen Sie mich wissen, wenn Sie irgendwelche Ideen haben.

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 
} 

Lassen Sie mich betonen, dass die Schulaufgabe für diejenigen, die in Zweifel sind, vorbei ist. Ich möchte das besser und effizienter machen. Ich kann mein Projekt auf gitHub veröffentlichen, wenn das helfen würde.

Answer 1

Ich bin zu faul, um Code im Moment zu schreiben, aber Sie sollten dies definitiv über Rekursion anstelle von sieben verschachtelten Schleifen tun können, und in der Tat sollten Sie in der Lage sein, eine Methode zu entwerfen, die auf jedem funktionieren sollte Telefonnummer beliebiger Länge.

Die Grundidee ist, dass Sie eine rekursive Methode so etwas wie dieses entwerfen würde:

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 
} 

Jedes Mal, wenn Sie Rekursion Sie auf der nächsten Zahlen-/Buchstabenposition arbeiten.

Natürlich, wenn Sie in die Beendigungsbedingung (sb Länge == Telefonlänge) laufen, dann schreiben Sie statt rekursiv nur den aktuellen Wert des StringBuilder in Datei und zurück.

Hoffe, das hilft.

Edit: Herumkommen, tatsächlich etwas Code zu schreiben. Es ist wirklich so einfach, keine LINQ erforderlich:

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

In diesem Code (wo ich eine einfache Konsolenanwendung gemacht) Ich bin nur die Worte, um die Konsole zu schreiben, aber man konnte die Saiten zu einem Array oder Schreiben des Hinzufügen sie stattdessen auf die Festplatte.

Answer 2

Hier Javaish pseudo-codeish rekursive Funktion:

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

Weitere excercises nach oben als C# zu schreiben und an Ihren Code anzupassen:

1. ändern buf von String einen gemeinsamen StringBuilder.
2. Dann wickeln Sie dies in Klasse und übergeben Sie nur Ind in Rekursion, haben die anderen als Klasse Elementvariablen.
3. Dann schließlich Rekursion in Schleife (Hinweis: 3 verschachtelte Schleifen, eine der inneren Schleifen wird zunehmende Anzahl von Iterationen haben).

Hinweis über nicht-rekursive Version Ich denke: Es weniger effizient als Rekursion sein wird, aber was macht es interessant und verdient Codierung als eine Übung ist, wird es breadth-first sein, während diese rekursive Version depth-first ist .

Answer 3

Ich habe die Annahme gemacht, dass Sie wahrscheinlich jede Ziffer auf sich selbst sowie alle normalen Buchstabenzuordnungen übersetzen möchten, plus Zuordnung 0 zu +. Also habe ich dieses Wörterbuch die Zuordnungen zu handhaben:

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"}, 
}; 

Meine permutate Funktion sieht dann wie folgt aus:

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

Das ist es.

Sie können es wie folgt verwenden:

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

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

Das Ergebnis ist eine Liste von Strings, wobei jeder String eine Permutation der Eingabenummer ist.

Wenn Sie Ziffern nicht zu Ziffern zuordnen möchten, nehmen Sie sie einfach aus der ursprünglichen Wörterbuchdefinition, aber Sie müssen ein einzelnes Zeichen für die Ziffer 1 beibehalten, damit es funktioniert.

Lassen Sie mich wissen, ob dies für Sie funktioniert.

Answer 4

Hier ist eine nicht-rekursive Lösung, dass

• eine Reihe gegeben, berechnet er das erste Wort für es
• ein Wort gegeben „Schritte“ es das nächste Wort finden

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

Genannt als z

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

Es könnte wahrscheinlich verwenden, um einige aufzuräumen, aber es ist eine allgemeine nicht-rekursive Lösung, die modifiziert werden kann, für ähnliche „Kreuzprodukt“ Situationen zu arbeiten.

Answer 5

Es tut mir leid, alle. Dies war mein erster Stack-Overflow-Post und ich erwartete eine E-Mail, wenn eine Antwort auf meine Frage gepostet wurde, bekam aber nie eine. Ich dachte nur, dass meine Frage in den Abgrund des Stapelüberlaufs geschluckt wurde.

Eine Gruppe von Entwicklern, mit denen ich arbeite, hat diese in etwa 5 Zeilen herausgefunden. Ich kann im Moment nicht die Lösung finden, aber ich denke, es war sehr nah an dem, was Enigmativity geschrieben hat. Ich bin positiv, dass wir Permutationen verwendet haben. Ich werde nach der Lösung suchen, die wir verwendet haben. Danke an alle.