C++ T9 Eingabe programmieren

[schneal76]

Hallo an alle!!
Bin neu hier und verzweifelt auf der suche nach einer Lösung meines Problems. Muss für die Schule T9 Eingabe nachprogrammieren (T9 = Worterkennung bei Handys)

Nun stehe ich vor dem Probelm, dass ich eine Funktion schreiben sollte, welche mir eine Zahlenfolge als String (z.b.:"5477") alle möglichen Kombinationen an Wörtern, sowohl sinnvolle als auch alle sinnlosen, liefert (jgpp..liss).

Hat wer eine Idee, wie ich das Problem lösen kann? Bitte um Hilfe, ich sitze schon seit Stunden an den Problem und komme einfach nicht darauf.

 

[godofkills]

Dafür brauchst du doch eine große Wöterliste die abgleicht, ob es für diese Zahlenkombination ein Wort bzw. mehre Wörter gibt.

 

[schneal76]

Das Ablgeichen mit einer Wörterbuchdatei mache ich dann später.
Zuerst will ich einmal eine Menge (set<string>) mit ALLEN möglichen Buchstabenkombinationen füllen. Das ist eigentlich mein Problem derzeit.

 

[F.b]

muss die funktion denn sein? wäre ein t9-wörterbuch nicht einfacher über eine baumstruktur zu realisieren?

 

[schneal76]

Leider ist es Teil der Aufgabe, eine Funktion zu entwickeln, welche ALLE möglichen Wörter der eingehenden String - Zeichenfolge (z.B.: "5477") in einer Datenstruktur abspeichert.

 

[mercsen]

eieieieie da werden aber viele werden!

möglich wäre es z.b. eine function zu schreiben die dir für jede taste die möglichen Buchstaben in einem Array zurückgibt und anschließend kombinierst du alle mit allen

z.B.
getBuchstaben(2) erzeugt einen Array (0=>D, 1=>E, 2=>F)
getBuchstaben(1) erzeugt einen Array (0=>A, 1=>B, 2=>C)

dann kombinierst du in einer schleife die Arrays

eingabe 12 hätte zur folge das
AD
AE
AF
BD
BE
BF
CD
CE
CF

eigentlich ist das recht simple zu bauen da du einfach nur jede kombination durchgehen musst.

 

[schneal76]

Naja, die Idee ist ja nicht schlecht, aber leider sind die Anzahl der Arrays == der Schleifen (durchläufe) nun ist es aber so, dass du angefangen von 2 Zahlen aufwärts jede Anzahl an Zahlen haben kannst.
Also habe ich nun einige Arrays mit den Werten gefüllt, aber dann weiter?

Meine erste Idee brachte mich zum Backtracking, aber das habe ich ehrlich gesagt nicht durchschaut
Andererseits bietet mir die STL ja eine tolle Funktion an zum Permutationen bestimmen, allerdings nur innerhalb einem Array, bzw. einer Menge.
Allerdings will ich die PErmutationen aus mehreren Mengen bekommen, einzige Bedingung ist, es muss aus jeder Menge 1 Element genommen werden und die Reihenfolge der Mengen darf sich auch nicht ändern.

 

[Raechaer]

Das schreit geradezu nach Rekursion:

1) Eine Funktion, die alle möglichen Wörter (bzw. Buchstaben) zu einem String mit der Länge 1 (also nur eine Taste!) liefert, kannst du ja bestimmt schreiben.

2) Für eine Eingabe mit Länge 2 gibst du alle möglichen Wörter (bzw. Buchstaben) für die erste Taste aus (ähnlich zu 1), und zusätzlich hängst du an jede dieser Möglichkeiten noch alle Wörter (bzw. Buchstaben) der Länge 1 für die 2. Taste an (das ist exakt das, was die Funktion aus 1) macht).

...

n) Für eine Eingabe mit Länge n gibst du alle möglichen Wörter (bzw. Buchstaben) für die erste Taste aus (ähnlich zu 1), und zusätzlich hängst du an jede dieser Möglichkeiten noch alle Wörter der Länge (n-1) für die restlichen (n-1) Tasten an (das ist exakt das, was die Funktion aus n-1) macht).

 

[schneal76]

Das schreit geradezu nach Rekursion:

1) Eine Funktion, die alle möglichen Wörter (bzw. Buchstaben) zu einem String mit der Länge 1 (also nur eine Taste!) liefert, kannst du ja bestimmt schreiben.

2) Für eine Eingabe mit Länge 2 gibst du alle möglichen Wörter (bzw. Buchstaben) für die erste Taste aus (ähnlich zu 1), und zusätzlich hängst du an jede dieser Möglichkeiten noch alle Wörter (bzw. Buchstaben) der Länge 1 für die 2. Taste an (das ist exakt das, was die Funktion aus 1) macht).

...

n) Für eine Eingabe mit Länge n gibst du alle möglichen Wörter (bzw. Buchstaben) für die erste Taste aus (ähnlich zu 1), und zusätzlich hängst du an jede dieser Möglichkeiten noch alle Wörter der Länge (n-1) für die restlichen (n-1) Tasten an (das ist exakt das, was die Funktion aus n-1) macht).


Sorry, aber ich habe echt keinen Plan, wie man das machen sollte. Vielleicht aber habe ich auch noch das Problem, dass ich eine MAP<char, char > > habe, wo ich in der ersten Stelle die Buchstaben von a bis z habe und an zweiter Stelle die Zahlen von 2 bis 9 habe.

 

[cx01]

Meine C++-Kenntnisse sind nicht sonderlich gut, daher hier mal eine simple Implementation in C#:

        private List<string> possibleChars(char x)
        {
            switch(x)
            {
                case '2': return new List<string> { "A", "B", "C" };
                case '3': return new List<string> { "D", "E", "F" };
                case '4': return new List<string> { "G", "H", "I" };
                case '5': return new List<string> { "J", "K", "L" };
                case '6': return new List<string> { "M", "N", "O" };
                case '7': return new List<string> { "P", "Q", "R", "S" };
                case '8': return new List<string> { "T", "U", "V" };
                case '9': return new List<string> { "W", "X", "Y", "Z" };
            }
            throw new Exception("invalid input");
        }

        private List<string> f(string input)
        {
            if (input.Length == 1) return possibleChars(input.First());

            List<string> p = possibleChars(input.First());
            List<string> rest = f(input.Substring(1));
            List<string> result = new List<string>();
            
            foreach(string y in p)
            {
                foreach (string z in rest)
                {
                    result.Add(y + z);
                }
            }

            return result;
        }

 

[Raechaer]

Sorry, aber ich habe echt keinen Plan, wie man das machen sollte. Vielleicht aber habe ich auch noch das Problem, dass ich eine MAP<char, char > > habe, wo ich in der ersten Stelle die Buchstaben von a bis z habe und an zweiter Stelle die Zahlen von 2 bis 9 habe.

Mach doch einfach genau das, was ich beschrieben habe.
Zuerst schreibst du eine Funktion, die dir zu einer Taste alle Möglichkeiten ausgibt (das ist nun wirklich trivial!).
Dann eine 2. Funktion für 2 Tasten, die wieder für die erste Taste alle Möglichkeiten ausgibt und zusätzlich an alle die Möglichkeiten mit der zweiten Taste anhängt (dafür kannst du die erste Funktion benutzen).
Dann eine 3. Funktion für 3 Tasten, die wieder für die erste Taste alle Möglichkeiten ausgibt und zusätzlich an alle die Möglichkeiten mit den zwei letzten Taste anhängt (dafür kannst du die zweite Funktion benutzen).

Und das machst du solange weiter, bis dir auffällt, dass diese Funktionen bis auf die Anzahl der übergebenen Tasten praktisch identisch sind. Dann machst du diese Anzahl variabel und schon hast du eine allgemeine Lösung.

Ich kann dir nur empfehlen, dass tatsächlich mal so zu machen, das hilft doch erheblich beim Verständnis für Rekursion und der Problem, die man damit elegant lösen kann. Falls du damit konkrete Probleme hast kann ich auch gerne helfen.
Falls es dir aber nur darum geht, die Aufgabe zu lösen ohne dabei etwas zu lernen, dann kannst du auch einfach die Lösung von cx01 kopieren...

 

[schneal76]

Herzlichen Dank für eure Unterstützung. Ich werde es mal mit raecher seiner Methode versuchen; lernen muss ich es sowieso irgendwie.
Und wenn alles nichts hilft, dann habe ich noch immer den fertigen Code hier.
Und im schlimmsten Fall melde ich mich noch einmal hier m Forum.

Auf alle Fälle herzlichsten Dank für eure Unterstützung