Alle Zeichenkombinationen eines Strings iterativ herausfinden

Hallo zusammen,
ich habe für ein Projekt eine Methode erstellt, die einen String erhält und alle möglichen Zeichenkombinationen in einer ArrayList zurückgibt (also bei String "abc": abc acb bac bca cab cba).
Ich habe das rekursiv gelöst und hier stellt sich mein Problem, nämlich der enorme Zeitaufwand, den die Methode benötigt. Da ich hintereinander 10-20 Strings mit einer Länge von 3-10 auf alle Zeichenkombinationen überprüfen muss, warte ich teilweise 1 oder 2 Minuten, bis ich ein Ergebnis erhalte.
Deshalb frage ich mich, wie man das iterativ lösen könnte, um die Zeit wenigstens zu verringern. Ich habe schon geknobelt, mir ist allerdings noch keine Lösung eingefallen, ich habe auch auf Foren noch keine gefunden.
Wenn irgendwer einen brillanten Einfall hat, wäre ich froh, wenn er ihn mitteilen könnte;).
Schon mal vielen Dank für die Hilfe,
Falkenauge
 
Ja, die Überprüfung würde mich auch mal interessieren. Spontan fällt mir nur ein, dass er entweder die Permutationen äußerst ineffizient erzeugt (daher die Vergleiche) oder völlig überflüssig (weil eine "Standardpermutation" = sortierte Zeichenkette) ausreichen würde.
 
Genau, zunächst muss klar sein, was du möchtest...

Ich sitze zu lange am PC.... Da will ich eine Permutation berechnen lassen, schreibe zwei rekursive und eine iterative Methode... und was kommt dabei heraus? Ein PRNG.
 
Erst einmal danke für die vielen Antworten.:)

Suche mal nach Permutationen oder Potenzmenge konstruieren...
Als ich danach gesucht habe, bin ich auf gute Ergebnisse gekommen.

Ja, die Überprüfung würde mich auch mal interessieren. Spontan fällt mir nur ein, dass er entweder die Permutationen äußerst ineffizient erzeugt (daher die Vergleiche) oder völlig überflüssig (weil eine "Standardpermutation" = sortierte Zeichenkette) ausreichen würde.
Also, ich brauche tatsächlich nicht alle, sondern lediglich alle unterschiedlichen (die Strings haben viele gleiche Chars, dementsprechend weniger unterschiedliche Möglichkeiten gibt es), mir war bisher aber auch keine Möglichkeit bewusst, alle unterschiedlichen Kombinationen herauszufinden, ohne alle auszuprobieren. Also eigentlich erzeuge ich schon viel überflüssig.

Ich werde die iterativen Lösungen, die ich beim Googlen von Permutation gefunden habe, ausprobieren und dann ein Update über die Zeitentwicklung geben.
 
Ach, diese GeeksForGeeks machen aber auch alles... @falkenauge05 Wenn das mit Strings und mit Rekursion zu langsam ist, dann würd ich das in JNI machen... aber das kann ich mir eigentlich gar nicht vorstellen. Beschreibe doch mal bitte mal etwas mehr, wie Dein Anwendungsfall schaut. Büdde.
 
Ach, diese GeeksForGeeks machen aber auch alles... @falkenauge05 Wenn das mit Strings und mit Rekursion zu langsam ist, dann würd ich das in JNI machen... aber das kann ich mir eigentlich gar nicht vorstellen. Beschreibe doch mal bitte mal etwas mehr, wie Dein Anwendungsfall schaut. Büdde.
Ich muss ein Wort mit einer gewissen Anzahl an Buchstaben in 2er oder 3er Blöcke aufteilen. Heißt, ich schaue zuerst, wie ich das Wort zerlegen kann (wie viele von 2er Block, wie viele von 3er Block). Dann muss ich überprüfen, welche Reihenfolge von 2er und 3er Blöcken am besten passt. Dafür brauche ich ja alle möglichen Reihenfolgen und deshalb muss ich die Lösungen, wie ich das Wort aufteilen kann, "permutieren", damit ich alle Möglichkeiten kenne und mit gewissen Kriterien überprüfen kann, welche Reihenfolge am besten passt.
 
Moin, also wenn alle Zeichen des Strings unterschiedlich sind (ie. "abcd" or "abcde") dann geht das so
Java:
public static LinkedList<String> per(String s) {
	LinkedList<String> list = new LinkedList<>();
	char[] a = s.toCharArray();
	int i = 1;
	int[] j = new int[a.length];
	while (i < a.length) {
		if (j[i] < i) {
			int k = ((i % 2) == 0) ? 0 : j[i]; // siehe StackOverflow

			// swapping
			char b = a[i];
			a[i] = a[k];
			a[k] = b;
			list.add(String.valueOf(a));

			j[i]++;
			i = 1;
		} else {
			j[i] = 0;
			i++;
		}
	}
	return list;
}

Quelle: https://stackoverflow.com/a/11916035 .

Ich kann Dir leider nicht genau sagen warum es funktioniert, ich weiß nur dass es funktioniert. :(
 
Also dann musst Du keinen einzelnen String übergeben, sondern ein Array von Strings... Der Algo der bleibt gleich.

Nebenbei.... Sind das Silben?

Bearbeitung, duden.de ist gerade nicht erreichbar, sonst hätte ich mich vergewissert, aber es scheinen keine Silben zu sein.
 
Zuletzt bearbeitet:
@Tobias-nrw Verstehst Du, was er eigentlich vor hat? Beispielsweise

@falkenauge05 Was heißt "am besten passt"? Mal anhand Deines Beispiels "Geburtstag", bitte :)
Es passt am besten, wenn möglichst wenig Vokale am Anfang der Blöcke stehen: Also bei "Geburtstag": "Ge" "bur" "ts" "tag". Hier sind nur Konsonanten am Anfang der Teilwörter.
Ich kann ja verstehen, dass es sehr nebulös ist ;). Das ist halt eine Aufgabenstellung für die Uni.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben