Alle Zeichenkombinationen eines Strings iterativ herausfinden

[falkenauge05]

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

 

[Xyz1]

Suche mal nach Permutationen oder Potenzmenge konstruieren...

 

[httpdigest]

Da ich hintereinander 10-20 Strings mit einer Länge von 3-10 auf alle Zeichenkombinationen überprüfen muss

Was genau überprüfst du denn da? Bzw. wofür genau benötigst du alle Permutationen der Characters in einem String? Vielleicht brauchst du ja gar nicht alle Permutationen zu generieren?

 

[mihe7]

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.

 

[Xyz1]

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.

 

[falkenauge05]

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.

 

[httpdigest]

Ja, aber wofür genau musst du denn die Permutationen generieren und was genau überprüfst du da? Eventuell geht das ja auch ohne irgendwelche Permutationen auszurechnen.

EDIT:
Google "distinct permutations java" -> https://www.geeksforgeeks.org/distinct-permutations-string-set-2/

 

[Xyz1]

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.

 

[falkenauge05]

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.

 

[httpdigest]

Ich geb auf. Das wird irgendwie immer nebulöser statt klarer. Was sind denn jetzt 2er und 3er Blöcke?

 

[Xyz1]

Moin, also wenn alle Zeichen des Strings unterschiedlich sind (ie. "abcd" or "abcde") dann geht das so

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.

 

[falkenauge05]

Ich geb auf. Das wird irgendwie immer nebulöser statt klarer. Was sind denn jetzt 2er und 3er Blöcke?

Blöcke aus 2 oder 3 Buchstaben, also bei Geburtstag z.B. "Geb" "ur" "tst" "ag" oder "Ge" "bu" "rt" "st" "ag"

 

[Xyz1]

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.

 

[mihe7]

Sind das Silben?

Nein.

 

[Xyz1]

Ge-burts-tag

 

[mihe7]

@Tobias-nrw Verstehst Du, was er eigentlich vor hat? Beispielsweise

Dann muss ich überprüfen, welche Reihenfolge von 2er und 3er Blöcken am besten passt.

@falkenauge05 Was heißt "am besten passt"? Mal anhand Deines Beispiels "Geburtstag", bitte

 

[Xyz1]

Verstehst Du, was er eigentlich vor hat

Ach so, nein, ich verstehe nicht wofür er es braucht Alles sehr nebulös....

 

[falkenauge05]

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

 

[mrBrown]

Wofür brauchst du da denn alle Permutationen? Da gibts doch deutlich sinnvollere Möglichkeiten

 

[mihe7]

Das würde ich allerdings auch sagen.

 

[Xyz1]

Verstehe immer noch nicht was "sinnvollere Möglichkeiten" wofür sein soll.

 

[mihe7]

Er soll ein Wort so in 2er-/3er-Gruppen zerlegen, dass die Gesamtzahl der Vokale am Anfang der Gruppen minimal ist.

 

[mrBrown]

Wobei ich mich noch Frage, ob das Wort einfach nur „zerschnitten“ werden soll, oder ob einfach nur die Buchstaben irgendwie in Gruppen angeordnet werden sollen. Der letzte Beitrag klang sehr nach erstem, da machen es Permutationen erstmal komplizierter...

 

[Meniskusschaden]

Ich kann ja verstehen, dass es sehr nebulös ist . Das ist halt eine Aufgabenstellung für die Uni.

Dort sind die Aufgabenstellungen in der Regel aber sehr präzise formuliert, vollständig und eindeutig. Also so ziemlich das Gegenteil von nebulös. Deine Aufgabenstellung ist dagegen auch nach inzwischen 25 Postings immer noch unklar. Könnte vielleicht an der Qualität deiner Übersetzung der Aufgabenstellung vom Uni- in's vermutete Forum-Niveau liegen.

 

[falkenauge05]

Wobei ich mich noch Frage, ob das Wort einfach nur „zerschnitten“ werden soll, oder ob einfach nur die Buchstaben irgendwie in Gruppen angeordnet werden sollen. Der letzte Beitrag klang sehr nach erstem, da machen es Permutationen erstmal komplizierter...

Es soll nur zerschnitten werden

 

[falkenauge05]

Wofür brauchst du da denn alle Permutationen? Da gibts doch deutlich sinnvollere Möglichkeiten

Mir sind halt bisher keine eingefallen, was gäbe es denn für Möglichkeiten?

 

[mrBrown]

Soll denn das Wort einfach nur zerschnitten werden?


Wie würdest du es denn "per Hand" machen, zB bei dem Wort Geburtstag?