Telefonnummern-Algorythmus

Status
Nicht offen für weitere Antworten.
J

jagdfalke

Bekanntes Mitglied
Hi, ihr kennt doch alle die Handytastaturen auf denen fast jeder Zahl 3 oder mehr Buchstaben zugeordnet sind:
1 = -
2 = abc
3 = def
usw.

Ich versuch einen Algorythmus zu schreiben, der mir aus einer Telefonnummer mit beliebiger Anzahl an Stellen alle Kombinationen in eine Liste schreibt. Ich scheitere aber an der Kombinationsfindung. Das Problem besteht eben darin, dass die Länge der Nummer beliebig sein soll.
Hat jemand mal was ähnliches gemacht? Ich find das total schwer, kenn da jemand helfen?

mfg
jagdfalke
 
L-ectron-X

L-ectron-X

Gesperrter Benutzer
Ich habs nicht ganz verstanden, vermute aber dass du ein Problem hast, die richtige Datenstruktur für deine Liste zu finden. Ein dynamisches Array, also eine Liste mit veränderlicher Größe wäre z.B ein Vector oder eine ArrayList.
 
G

Guest

Gast
ich glaube das ist alles falsch:
angenommen die nummer lautet 23:
a
ad,
ae,
af,
bd
be
bf,
cd,
ce,
cf

Ihr kennt doch sicher so Werbung im TV in der dann in der Telefonnummer Wörter stehen (z.B.: 0190SEXSEX66 = 019073973966 (SEX = 739)). Ich möchte in meinem Programm solche Wörter finden.
 
J

jagdfalke

Bekanntes Mitglied
das ist richtig. mit einer Ziffer ist es leicht. Aber ich steig da nicht durch wie das rekursiv funzt.
Code: 
String combo;
String[] num_to_char = {  {"", "", "", ""},
                                       {"", "", "", ""},
                                       {"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"}  };

public void getCombos(int[] numbers) {
        int first_num =  numbers[0];   //erste Ziffer holen
        
        //hier irgendwas machen

        int[] new_numbers = new int[numbers.length()-1];   // neues array anlegen (1 kürzer als numbers)
        for(int i=1; i<numbers.length(); i++) {                    // array numbers um die erste zahl
                new_numbers[i-1] = numbers[i];                     // die erste zahl
        }                                                                           // kürzen
        getCombos(new_numbers);                                     // funktion ruft sich selber auf
}


bei der Stelle "//hier irgendwas machen" komm ich nicht mehr weiter, kann jemand helfen? Oder ist es ein ganz falscher Ansatz?

mfg
jagdfalke
 
clemson

clemson

Bekanntes Mitglied
ich würd das ganze irgendwie so lösen:

es gibt ein objekt "zifferntaste" welches die einzelnen werte einer taste speichert - falls nötig auch noch den eigentlichen wert (bsp.: a,b,c & 2).

weiters gibt es ein objekt "ziffernblock", welches die einzelnen tasten speichert...

allgemeine überlegung:

wie Bleiglanz schon sagte, rekursiv ist, denke ich auch, die lösung. überlege dir, wie du für eine taste alle kombinationen bekommen würdest...

auf meine eingangsüberlegung übetragen: jede zifferntaste hat eine methode, welche dir die kombinationen der jeweiligen buchstaben zurückgibt.

das ziffernblock-objekt hat wiederum eine methode, welche alle kombinationen der einzelnen tasten zusammenfügt (zuerst alle kombinationen der taste 1 durchlaufen, und die "standardkombination" der einzelnen tasten anfügen. dann die standardkombination der ersten taste + kombinationen der 2. taste + standardkombinationen der anderen tasten)...
 
G

Guest

Gast
Hä? Was meinst du immer mit "alle kombinationen" einer Taste ??? Das drücken einer Taste erzeugt doch noch keine Kombination. Die Methode die die "Kombination" zurückgibt müsste dann ein Array mit 3 oder 4 Elementen zurückgeben, die dann mit dem bereits erstellten String kompiniert werden. Aber ich ich jetzt ne ganze Klasse schreibe um die möglichen Buchstaben einer Ziffer zu bekommen oder ob ich das in einem Array speicher is doch egal.
Code: 
String[] num_to_char = 
{  
{"", "", "", ""},    //0
{"", "", "", ""},    //1
{"a", "b", "c", ""},    //2
{"d", "e", "f", ""},    //3
{"g", "h", "i", ""},    //4
{"j", "k", "l", ""},    //5
 {"m", "n", "o", ""},    //6
 {"p", "q", "r", "s"},    //7
{"t", "u", "v", ""},    //8
{"w", "x", "y", "z"}      //9
};

die möglichen Combos holt man sich dann so:
Code: 
num_to_char[momentane_Ziffer][i]

Ich hab hier mal was geschrieben, es ergibt aber noch nicht ganz das gewünschte Ergebnis:

getAllCombos(int, String) wird mit 0 und "" aufgerufen.
Code: 
	String[][] tabelle = {	{"",  "",  "",  ""},		// 0
				{"",  "",  "",  ""},		// 1
				{"a", "b", "c", ""},		// 2
				{"d", "e", "f", ""},		// 3
				{"g", "h", "i", ""},		// 4
				{"j", "k", "l", ""},		// 5
				{"m", "n", "o", ""},		// 6
				{"p", "q", "r", "s"},		// 7
				{"t", "u", "v", ""},		// 8
				{"w", "x", "y", "z"}	};	// 9
	int[] numbers;
	int run_thru;

	public void getAllCombos(int ran_thru, String combo) {

		if(ran_thru <= run_thru) {
			combo += tabelle[numbers[ran_thru]][0];
			listModel.addElement(combo);
			getAllCombos(ran_thru+1, combo);

			combo += tabelle[numbers[ran_thru]][1];
			listModel.addElement(combo);
			getAllCombos(ran_thru+1, combo);

			combo += tabelle[numbers[ran_thru]][2];
			listModel.addElement(combo);
			getAllCombos(ran_thru+1, combo);
		}

	}

Das Ergebnis der Ziffern 2 und 3 ist:
a
ad
ade
adef
ab
abd
abde
abdef
abc
abcd
abcde
abcdef
Zum Vergrößern anklicken....
es sollte aber so aussehen:
a
ad
ae
af
bd
be
bf
cd
ce
cf
Zum Vergrößern anklicken....

also man sieht schon, dass das Ergebnis nichts damit zu hat, wie es aussehen sollte. Wo ist mein Denkfehler? Ich werd noch verrückt mit dem Zeug.

mfg
jagdfalke
 
clemson

clemson

Bekanntes Mitglied
Anonymous hat gesagt.:
Hä? Was meinst du immer mit "alle kombinationen" einer Taste ??? Das drücken einer Taste erzeugt doch noch keine Kombination. Die Methode die die "Kombination" zurückgibt müsste dann ein Array mit 3 oder 4 Elementen zurückgeben, die dann mit dem bereits erstellten String kompiniert werden. Aber ich ich jetzt ne ganze Klasse schreibe um die möglichen Buchstaben einer Ziffer zu bekommen oder ob ich das in einem Array speicher is doch egal.
Zum Vergrößern anklicken....

hmm, du hast recht... war ein denkfehler von mir ;)
 
P

PyroPi

Aktives Mitglied
Irgendwie verstehe ich das geforderte Ergebnis nicht so recht:

a
ad
ae
af
bd
be
bf
cd
ce
cf
Zum Vergrößern anklicken....

Wieso steht da ein "a" allein am Anfang? Entweder fehlt dann auch noch ein "b" und ein "c", oder das müßte ganz weg.

Meine Idee wäre folgende: Die getAllCombos-Methode bekommt den aktuellen Input-String (also die Zahlenkette) als Parameter übergeben. Ist der Input-String leer, so beendet die Methode und gibt einen Vector mit einem leeren String zurück. Sonst nehme man sich die erste Ziffer vom Input-String, ermittelt die möglichen Buchstaben dafür und legt diese in einem neuen Vector vecA als einzelne Strings ab. Durch Rekursion erhält man alle Wörter, die aus dem übergebenen Input-String ohne den ersten Buchstaben entstehen. Diese könnte man bswp. in einem Vector vecB zwischenspeichern. Nun muß nur noch das Komplexprodukt von vecA und vecB gebildet werden, d.h. es wird ein neuer Vector vecC erzeugt, der alle Verkettungen von einem String aus vecA und einem String aus vecB beinhaltet (z.B. {"a", "b"}*{"1", "2"} = {"a1", "a2", "b1", "b2"}). Dieser Vector vecC ist nun der Rückgabewert der Methode getAllCombos.

Das ganze ist jetzt wahrscheinlich nicht gerade die speichereffizienteste Methode, aber sie sollte zumindest das gewünschte Ergebnis erzeugen.

Liebe Grüße,

PyroPi
 
Bleiglanz

Bleiglanz

Gesperrter Benutzer
angenommen die telnr lautet 1234

für 234 hast du rekursiv schon alles berechnet (sagen wir eine ArrayList<String>)

dann musst du jetzt einfach

für alle berechneten Strings in der ArrayList

jeweils ein a vornedran

jeweils ein b vornedran

jeweils ein c vornedran

(also eine doppelte schleife über die schon bekannten ergebnisse und alle erlaubten buchstaben, das verdreifacht die anzahl der möglichkeiten)

also einfach

Code: 
public ArrayList<String> findeKombis(String telnr)
{
     n = telnr.length();
     wenn n==1, dann nimm die für diese ziffer erlaubten und leg sie als string in die arrayList
     return diese

      wenn n>1
       rekursiveListe = findeKombis(telnr.substring(1))
        neueListe = new ArrayList
       for alle s in der rekursiveListe
         for alle buchstaben x die für substring(0,1) erlaubt sind
                 neueListe.add(x+s);
          }
        }
        return neueListe
}

[Edit by Beni: Codetags, und das bei unserem Lieblingsuser :-O]
 
Status
Nicht offen für weitere Antworten.

Aktuelle Jobs

Neue Themen


Oben