Alle Zeichenkombinationen eines Strings iterativ herausfinden

F

falkenauge05

Mitglied
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
 
H

httpdigest

Top Contributor
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

mihe7

Top Contributor
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.
 
X

Xyz1

Gast
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.
 
F

falkenauge05

Mitglied
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.
 
X

Xyz1

Gast
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.
 
F

falkenauge05

Mitglied
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.
 
H

httpdigest

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

Xyz1

Gast
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. :(
 
X

Xyz1

Gast
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 von einem Moderator:
F

falkenauge05

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

mrBrown

Super-Moderator
Mitarbeiter
Wofür brauchst du da denn alle Permutationen? Da gibts doch deutlich sinnvollere Möglichkeiten :)
 
mihe7

mihe7

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

mrBrown

Super-Moderator
Mitarbeiter
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...
 
M

Meniskusschaden

Top Contributor
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.;)
 
F

falkenauge05

Mitglied
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
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Soll denn das Wort einfach nur zerschnitten werden?


Wie würdest du es denn "per Hand" machen, zB bei dem Wort Geburtstag? ;)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
E Wie gebe ich alle Daten zwischen zwei Zeitpunkten aus? Java Basics - Anfänger-Themen 2
crrnogorka Letzte Zeile einer Tabelle "überschreibt" alle anderen Zeilen Java Basics - Anfänger-Themen 1
C alle möglichen Kombinationen zweier Ziffern auf drei / vier / und 'n" Stellen Java Basics - Anfänger-Themen 11
H Alle Geraden zahlen bis 10 ausgeben Java Basics - Anfänger-Themen 11
L Alle Ziele in einem Raster abknallen Java Basics - Anfänger-Themen 17
J Alle Werte eines Strings zusammen addieren Java Basics - Anfänger-Themen 15
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
B Alle Links in einem Text suchen und ersetzen mit einem neuen Link Java Basics - Anfänger-Themen 18
K Array alle Werte aufsummieren und ausgeben Java Basics - Anfänger-Themen 6
Dimax Erste Schritte String replace alle Zeichen Java Basics - Anfänger-Themen 10
L Wie vergrößere ich ein Rechteck in alle Richtungen um eins und bekomme dessen Rand? Java Basics - Anfänger-Themen 2
L Breadth-First Search statt einem Pfad, alle Pfade herausfinden Java Basics - Anfänger-Themen 4
X Erste Schritte String: Alle doppelten Leerzeilen entfernen Java Basics - Anfänger-Themen 21
M Regex-Ausdruck: Alle Zeichen bis auf ein bestimmtes erlauben (p{L}) Java Basics - Anfänger-Themen 5
I Alle Elemente von zwei Listen vergleichen Java Basics - Anfänger-Themen 1
Kirby.exe Alle möglichen Error Möglichkeiten abfangen Java Basics - Anfänger-Themen 33
M Unterklasse soll nicht alle Methoden erben Java Basics - Anfänger-Themen 3
V Erste Schritte for-Schleife; Ausgabe soll alle 5 Sekunden erfolgen. Java Basics - Anfänger-Themen 4
A Alle true Werte eines boolean Arrays herausfiltern Java Basics - Anfänger-Themen 19
D Alle Möglichkeiten, n-Anzahl aus Elementen aus einem Array zu wählen, ausgeben? Java Basics - Anfänger-Themen 23
M prüfen ob alle array werte gleich sind Java Basics - Anfänger-Themen 27
L Classpath Alle Dateien im Classpath finden Java Basics - Anfänger-Themen 4
G Überprüfen ob alle Ziffern von 1-9 in einem Integer vorhanden sind Java Basics - Anfänger-Themen 6
J Erste Schritte Alle möglichen ausgaben von 5 Zahlen als Vector Java Basics - Anfänger-Themen 7
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
D Methoden Eigene Methode um alle Ausgaben aufzurufen Java Basics - Anfänger-Themen 17
F Ordner auf alle Unterdatein abfragen Java Basics - Anfänger-Themen 3
A In einem String alle Eigennamen zählen Java Basics - Anfänger-Themen 6
B Klassen Alle Unter-Objekte durchlaufen in der Hauptklasse Java Basics - Anfänger-Themen 10
W ArrayList löscht alle Elemente bis auf eines Java Basics - Anfänger-Themen 2
B Webservice -> alle parameter bekommen von form Java Basics - Anfänger-Themen 2
das_leon Alle Zeilen einer CSV-Datei auslesen Java Basics - Anfänger-Themen 1
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
F Eclipse alle Projekt weg Java Basics - Anfänger-Themen 6
V Alle Komponenten eines JPanels Java Basics - Anfänger-Themen 14
I gemeinsame Config-Datei für alle Windows-User Java Basics - Anfänger-Themen 5
H JButton - Wechsel der Textfarbe alle 500ms Java Basics - Anfänger-Themen 10
DaCrazyJavaExpert Alle Zahlenkombinationen aus 9 zahlen finden Java Basics - Anfänger-Themen 17
F Alle Objekte einer Klasse nach Eigenschaft durchsuchen Java Basics - Anfänger-Themen 8
M Alle Instanzen einer Klasse ansprechen Java Basics - Anfänger-Themen 4
S Problem: Array alle Einträge gleich Java Basics - Anfänger-Themen 10
Z Enter Taste alle 0,5 Sekunden ausführen Java Basics - Anfänger-Themen 1
U RegEx alle Kommas bei den Zahlen in Punkt umwandeln Java Basics - Anfänger-Themen 3
K alle Vorkommen einer bestimmten Ziffer in einer Zahl zählen Java Basics - Anfänger-Themen 2
X Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen Java Basics - Anfänger-Themen 1
C Alle Zweierpotenzen bis 2^10 ausgeben lassen Java Basics - Anfänger-Themen 15
B Alle Attribute von Klasse bekommen und ändern Java Basics - Anfänger-Themen 12
M Input/Output Alle Zeilen auslesen und in Variable speichern Java Basics - Anfänger-Themen 5
W Mozilla Thunderbird email an alle Kontakte Java Basics - Anfänger-Themen 3
F Methode alle 15min ausführen Java Basics - Anfänger-Themen 5
D Alle möglichen Kombinationen in einem Array ausgeben Java Basics - Anfänger-Themen 2
I Alle Laufwerke und deres Pfade ausgeben Java Basics - Anfänger-Themen 6
S Classpath: Alle .jars innerhalb eines Ordners einbinden Java Basics - Anfänger-Themen 4
G Alle Objekte und Variablen automatisch ausgeben Java Basics - Anfänger-Themen 7
I Programm, welches eine Textzeile einliest und alle darin enthaltenen Buchstaben umwandelt Java Basics - Anfänger-Themen 3
G Wie bekomme ich alle Ausgaben von runTime.exec() Java Basics - Anfänger-Themen 7
L Best Practice Alle Kombinationen aus Listenelementen, Anzahl Listen unterschiedlich Java Basics - Anfänger-Themen 6
M Compiler-Fehler Alle Methoden eines Interfaces Implementiert dennoch Fehler Java Basics - Anfänger-Themen 3
I Alle Zeitzonen in Liste speichern Java Basics - Anfänger-Themen 4
F alle 100ms Befehle ausführen Java Basics - Anfänger-Themen 26
M Alle Sublisten einer bestimmten Laenge berechnen Java Basics - Anfänger-Themen 2
F Alle DEMOS fast veraltet...? Java Basics - Anfänger-Themen 13
J Alle Leerzeichen aus String entfernen Java Basics - Anfänger-Themen 13
D Methoden Alle Siebenstelligen Primpalidrome von PI Java Basics - Anfänger-Themen 6
K Durch alle Attribute eines Objektes iterieren Java Basics - Anfänger-Themen 6
P Klassen Alle Strings einer ArrayList<eigeneKlasse> anspre Java Basics - Anfänger-Themen 2
W String von hinten alle drei Zeichen abschneiden und in umgekehrter Reihenfolge ausgeben. Java Basics - Anfänger-Themen 9
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
M Alle möglichen Strings Java Basics - Anfänger-Themen 5
J Alle Wörter der Länge n mit 0 und 1 Java Basics - Anfänger-Themen 17
T Alle Threads .notify() Java Basics - Anfänger-Themen 13
G Methoden Alle Objekte der ArrayList ausgeben funktioniert nicht. Java Basics - Anfänger-Themen 12
N Klassen Class nur einmal ausführen und sie speichert daten für alle anderen classes? Java Basics - Anfänger-Themen 3
M Klassen Auf Alle Array Methoden gleichzeitig zugreifen Java Basics - Anfänger-Themen 8
D Frame schließt gleich alle Frames Java Basics - Anfänger-Themen 5
T Wie mache ich einen Timer der alle 2 sekunden aufgerufen wird? Java Basics - Anfänger-Themen 5
D JFileChooser "alle Dateien" unterbinden Java Basics - Anfänger-Themen 3
S Aus zwei Dateipfaden alle Dateien auslesen Java Basics - Anfänger-Themen 11
B Frage zur Effizienz - alle Array-Felder initialisieren oder jedes Feld auf null prüfen? Java Basics - Anfänger-Themen 4
F Geht in alle Case rein, warum?? Java Basics - Anfänger-Themen 12
R Alle Klassen ermitteln, die Interface implementieren / Reflection Java Basics - Anfänger-Themen 51
M Primzahlen - es werden alle Nicht-Primzahlen ausgegeben Java Basics - Anfänger-Themen 5
L RandomAccessFile liest nicht alle Zeichen Java Basics - Anfänger-Themen 3
S Warten bis alle Threads fertig sind Java Basics - Anfänger-Themen 12
M Class will alle Variablen als static haben Java Basics - Anfänger-Themen 11
E Erste Schritte Eclipse kompiliert alle Projekte im Workspace Java Basics - Anfänger-Themen 10
J Alle Vorkommen eines chars in einem Array durch einen anderen char ersetzen Java Basics - Anfänger-Themen 10
S Alle 60min prüfen ob eine Datei da ist Java Basics - Anfänger-Themen 6
Dit_ Funktion alle 24 Stunden ein mal aufrufen Java Basics - Anfänger-Themen 3
Dit_ Input/Output Alle Exceptions protokollieren Java Basics - Anfänger-Themen 9
S Regex - alle Matches ausgeben? Java Basics - Anfänger-Themen 2
2 Alle Werte die mit n Würfeln mit m Seiten geworfen werden können in ein n Dimensionales Array Java Basics - Anfänger-Themen 15
B Alle Benutzer anzeigen Java Basics - Anfänger-Themen 17
S Suchmaske alle Möglichkeiten effinzent durchgehen Java Basics - Anfänger-Themen 4
R Kurze Linien alle x-Pixel Java Basics - Anfänger-Themen 2
K Alle vorkommen eines Zeichens in StringBuffer Objekt löschen Java Basics - Anfänger-Themen 6
D X Werte in ArrayList von Point Objekte alle gleich ? Java Basics - Anfänger-Themen 11
H Alle Array-Elemente auf einmal überprüfen? Java Basics - Anfänger-Themen 10
R Alle Daten einer HashMap ausgeben Java Basics - Anfänger-Themen 17
S mysql-connector-java-*.jar, MySql ResultSet - Alle ROWs ausgeben? Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Anzeige

Neue Themen


Oben