Próba rozwiązania bardziej eleganckiego słowa telefonicznego z rekursją

Question

Przeglądałem Stack Overflow, ale nie udało mi się uzyskać niczego do pracy. Przepraszam, jeśli przegapiłem oczywisty post.

Miałem problem szkolny polegający na zabraniu numeru telefonu, uzyskaniu wszystkich możliwych kombinacji słów, a następnie zapisaniu go do pliku tekstowego. Zrobiłem to i dostałem pełny kredyt za moje zadanie. Udało mi się to zrobić z siedmioma zagnieżdżonymi pętlami, ale to nie jest zbyt eleganckie i bardzo sztywne. Byłem zszokowany i całkowicie rozczarowany, że znalazłem rozwiązanie w postaci podręcznika w siedmiu zagnieżdżonych pętlach. Mój instruktor także nie miał odpowiedzi.

Próbowałem wielu różnych podejść, ale nie byłem w stanie go wybrać. Zidentyfikowałem rekursję i punkt zabicia, ale nigdy nie byłem w stanie go uruchomić. Mogę wytworzyć sekwencje liter, ale nigdzie w pobliżu, ile powinno być. Skomentowałem moje próby, abyś mógł zobaczyć moje nieudane procesy myślowe :) Proszę spojrzeć i daj mi znać, jeśli masz jakieś pomysły.

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 
} 

Pozwolę sobie podkreślić, że zadanie szkolne zostało zakończone dla tych, którzy mają wątpliwości. Chcę to zrobić lepiej i wydajniej. Mogę opublikować mój projekt na gitHub, jeśli to pomogłoby.

Answer 1

Jestem zbyt leniwy, aby napisać dowolny kod w tej chwili, ale zdecydowanie powinieneś być w stanie to zrobić przez rekursję zamiast siedmiu zagnieżdżonych pętli, i faktycznie powinieneś być w stanie zaprojektować metodę, która powinna działać na dowolnym arbitralna długość numeru telefonu.

Podstawowym założeniem jest to, że można zaprojektować rekurencyjnej metody coś takiego:

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 
} 

Każdorazowe recurse pracujesz na stanowisku obok/numer listu.

Oczywiście, jeśli napotkasz warunek zakończenia (długość sb == długość telefonu), zamiast powtarzać, po prostu napisz aktualną wartość StringBuilder do pliku i zwróć.

Mam nadzieję, że to pomoże.

Edytuj: Poruszanie się po to, aby napisać jakiś kod. To naprawdę to proste, nie LINQ wymagane:

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

W tym kodzie (gdzie zrobiłem prostą aplikację konsoli) Jestem po prostu pisząc te słowa do konsoli, ale mogłoby być dodanie ciągi do tablicy lub pisemnie je zamiast tego na dysku.

Answer 2

Oto Javaish pseudo-codeish rekurencyjna funkcja:

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

Kolejne ćwiczenia po napisaniu powyżej jak C# i dostosowania go do kodu:

1. Zmień buf od String jeden wspólny StringBuilder.
2. Następnie zawiń to do klasy i przeprowadź tylko ind w rekursji, pozostałe jako zmienne składowe klasy .
3. Następnie w końcu przekształć rekurencję w pętlę (wskazówka: 3 zagnieżdżone pętle, jedna z wewnętrznych pętli będzie miała zwiększoną liczbę iteracji).

Informacja o wersji non-rekurencyjne myślę: To będzie mniej wydajny niż rekursji, ale to, co sprawia, że ​​jest ciekawy i godny kodowanie jako ćwiczenie jest, to będzie breadth-first, podczas gdy wersja rekurencyjna jest depth-first .

Answer 3

Podjęłam założenie, że prawdopodobnie chcesz przetłumaczyć każdą cyfrę na siebie oraz wszystkie normalne odwzorowania liter, a także mapować 0 na +. Więc zrobiłem tego słownika do obsługi mapowania:

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

Moja funkcja permutate wtedy wygląda tak:

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

To wszystko.

Można go używać tak:

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

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

Rezultatem jest lista ciągów gdzie każdy ciąg jest permutacją liczby wejściowej.

Jeśli nie chcesz zamieniać cyfr na cyfry, po prostu wyjmij je z pierwotnej definicji słownika, ale musisz zachować pojedynczy znak dla cyfry 1, aby działał.

Daj mi znać, jeśli to działa dla Ciebie.

Answer 4

Oto nierekursywnych rozwiązanie, które

• Biorąc pod uwagę liczbę, oblicza pierwsze słowo
• otrzymał słowo „przyrosty” to, aby znaleźć następny wyraz

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

Zwany jako eg

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

To prawdopodobnie mogłyby korzystać z niektórych sprzątania, ale jest to rozwiązanie ogólne nierekursywnych które mogą być modyfikowane, aby pracować dla podobnych sytuacjach „cross produktów”.

Answer 5

Przykro mi wszystkim. To był mój pierwszy post przepełnienia stosu i spodziewałem się e-maila, gdy odpowiedź została zaksięgowana na moje pytanie, ale nigdy jej nie dostałem. Po prostu uznałem, że moje pytanie zostało połknięte w otchłani przepełnienia stosu.

Grupa deweloperów, z którymi pracuję, została opracowana w około 5 liniach. Nie mogę znaleźć rozwiązania w tej chwili, ale myślę, że było bardzo blisko tego, co napisała Enigmativity. Jestem pewien, że użyliśmy permutacji. Poszukam rozwiązania, którego użyliśmy. Dziękuję wszystkim.