# Telefonnummern-Algorythmus



## jagdfalke (16. Aug 2005)

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 (16. Aug 2005)

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.


----------



## bygones (16. Aug 2005)

meinst du folgendes:

Nr: 2

ergebnis: abc, acb, bac, bca, cab, cba

?

zum thema Kombination gibt es folgenden Thread:
http://www.java-forum.org/de/viewtopic.php?t=20939&highlight=kombination


----------



## Guest (16. Aug 2005)

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.


----------



## jagdfalke (16. Aug 2005)

Hat keiner nen Tip?


----------



## Bleiglanz (16. Aug 2005)

machs halt rekursiv

für eine telefonnummer mit nur einer ziffer ists ja leicht


----------



## jagdfalke (16. Aug 2005)

das ist richtig. mit einer Ziffer ist es leicht. Aber ich steig da nicht durch wie das rekursiv funzt.

```
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 (16. Aug 2005)

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)...


----------



## Guest (16. Aug 2005)

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.

```
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:

```
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. 

```
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
> ...


es sollte aber so aussehen:


> a
> ad
> ae
> af
> ...



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 (16. Aug 2005)

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.



hmm, du hast recht... war ein denkfehler von mir


----------



## jagdfalke (16. Aug 2005)

Sonst noch Vorschläge?


----------



## PyroPi (17. Aug 2005)

Irgendwie verstehe ich das geforderte Ergebnis nicht so recht:



> a
> ad
> ae
> af
> ...



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 (17. Aug 2005)

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


```
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]_


----------



## daLenz (17. Aug 2005)

Hi, sieh dir mal diese seite an, könnte dir weiterhelfen:

http://www.merriampark.com/comb.htm

greetz


----------

