Permutation / Kombination

[sklay]

Moin,

ich habe einen zufällig mit Buchstaben gefüllten String und will alle Möglichkeiten erhalten, die sich aus diesen Buchstaben ergeben. Auch die Möglichkeiten, die weniger Buchstaben als die maximale Anzahl an Buchstaben beinhalten.

Beispiel: String ist "abcd". Lösung:
"a"
"b"
"c"
"d"
"ab"
"ac"
"ad"
"ba"
"bc"
"bd"
"ca"
"cb"
"cd"
"da"
"db"
"dc"
"abc"
...
usw.

enriico hat hier (www.java-forum.org/de/viewtopic.php?t=43031) ja einen schönen Code gepostet. Aber irgendwie verstehe ich den Code nicht.

Überall finde ich nur Beispiele bei einer festen Länge. Die Beispiele sind mir aber auch meist viel zu kompliziert und gehen weit über meinen Wissensstand bei Java.

Kann man mir einen einfachen Lösungsvorschlag geben?

 

[0x7F800000]

was enriico da geschriebn hat waren aber die permutationen, also sequenzen mit fester länge, du brauchst hier dagegen alle kombinationen aller längen, das ist imho bissl anders...

ich hab hier eben folgendes gebastelt:

import java.util.*;

public class Combinatorics{

public static void calculateAllCombinations(String availableSymbols,
									 String baseString, 
									 int length,
									 LinkedList<String> list){
	if(length==0){
		//rekursionsende
		list.add(baseString);
	}else{
		//jeweils ein symbol dranhängen, und rekursiv sich selbst aufrufen
		for(int i=0; i<availableSymbols.length(); i++){
			char c=availableSymbols.charAt(i);
			if(baseString.indexOf(c)<0){
				calculateAllCombinations(availableSymbols,
										 baseString+c,
										 length-1,
										 list);
			}
		}
	}
}
	
public static void main(String[] args){
	String availableSymbols="abcd";
	
	LinkedList<String> combinationsList=new LinkedList<String>();
	
	//berechnen
	for(int len=1; 
		len<=availableSymbols.length(); 
		len++){
		
		calculateAllCombinations(availableSymbols,
								 "",
								 len,
								 combinationsList);
	}
	
	//ausgeben
	ListIterator<String> it=combinationsList.listIterator(0);
	
	while(it.hasNext()){
		System.out.print(it.next()+" ");
	}
}
}

läuft wunderbar:

a b c d ab ac ad ba bc bd ca cb cd da db dc abc abd acb acd adb adc bac bad bca bcd bda bdc cab cad cba cbd cda cdb dab dac dba dbc dca dcb abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba

zum prinzip ist eigentlich nicht viel zu sagen: du schnappst dir halt nacheinander alle buchstaben aus dem haufen der verfügbaren buchstaben, die noch nicht benutzt wurden, so oft, bis du eine zeichenkette der gewünschten länge erhalten hast... das machst du für alle längen.

 

[sklay]

Andrey, du bist fantastisch. Dein Code ist einfach, übersichtlich und verständlich. LinkedList kannte ich noch nicht, weil ich wie gesagt noch ziemlich unerfahren in Java bin.

Ich habe noch ein paar kleine Verständnisfragen, die mir das Internet irgendwie nicht so ganz beantworten kann:

Eine LinkedList ist also ein dynamischer doppeltverketterer Array?
Und wenn ich dahinter <String> schreibe, heißt es, dass die Elemente in diesem Array alle vom Typ String sind?
Wenn ich also

LinkedList<int> combinationsList=new LinkedList<int>();

schreibe, habe ich eine Liste mit int-Werten?

ListIterator<String> it=combinationsList.listIterator(0);

erstellt einen Zeiger, mit dem ich durch die Liste (in beide Richtungen) laufen kann?

Danke für die schnelle Hilfe.

 

[0x7F800000]

Nein, LinkedList ist der krasse gegensatz zu einem array
Bei arrays liegen alle abgespeicherten elemente alle nacheinander in einem zusammenhängenden block im speicher. Wenn man da ein element mittendrin einfügen will, muss man speicher neu allokieren, alles irgendwie verschwieben und rüberkopieren (dauert ewig, auch wenn da i.d.R nur kurze referenzen drin gespeichert sind) dafür gibts da schnellen random access.

Bei der Linked list gibts kein random access, aber dafür muss man zum einfügen von elementen grad mal 2-4 referenzen umbiegen, das ist wesentlich schneller.

aber damit ich hier nicht wieder anfange alles von anfang an zu erzählen: deathbyaclown hat das schon alles super erklärt, siehe FAQ:
http://www.java-forum.org/de/viewtopic.php?p=117258

noch was zu <int> als typ: afaik geht das mit primitiven datentypen nicht, sondern nur mit Objekten. Bei primitiven muss du da drumherumwrappen.

und das mit dem Iterator hast du wahrscheinlich auch richtig gemeint. Wie ich das aber korrekt mit fachsprache beschreibe: kA... So als "Zeiger" darf man in Java eh nix bezeichnen, aber in C++ sehen zeiger und iteratoren rein äuserlich zumindest recht ähnlich aus...