Finde alle Permutationen eines gegebenen Strings in Java
![Finde alle Permutationen eines gegebenen Strings in Java](/img/Java/feature-image---permutations-of-a-string-java.webp)
Die Permutation ist die mathematische Technik, um die Anzahl möglicher Anordnungen in einer Menge zu bestimmen, wenn die Reihenfolge der Anordnung von Bedeutung ist.
Permutationen einer Zeichenkette mit Rekursion
Die Funktion permutationFinder(String str)
ist rekursiv und gibt jede Permutation des übergebenen Strings aus. Die Variable Set
wird verwendet, um die Permutationen eines Java-Strings zu speichern, damit Duplikate automatisch entfernt werden. Wir zerhacken unsere Wörter, nehmen einen Buchstaben nach dem anderen in unsere Zeichenkette und behandeln die verbleibenden Buchstaben getrennt.
Die Funktion insertChar
fügt das erste Zeichen ein, um die vollständige Liste der Permutationen für den übergebenen String zu erhalten.
Wir beginnen mit der Zeichenkette “ABC”, wir durchlaufen sie Buchstabe für Buchstabe. Wir trennen unser Anfangszeichen A
und die restlichen sind BC
. Nun iterieren wir durch das rem
und finden die Permutationen für die restlichen Buchstaben. Der Vorgang wird weiter unten erläutert.
Die Funktion permutationFinder()
wird gefeuert, bis wir nichts zu hacken haben; deshalb erhalten wir rem = ""
. An dieser Stelle fügen wir ""
zu perms
hinzu und geben es zurück, das weiter in der Variable Set
words
gespeichert wird. Denken Sie auch daran, dass unser Anfangszeichen
in diesem Moment C
ist.
Wir durchlaufen jeden String in den Set
-Wörtern. Wir haben strNew
als den leeren ""
-String, in diesem Fall geht es bis zur zweiten for-Schleife, wir haben i=0
, was gleich strNew.length()
ist; Daher rufen wir die Methode insertChar("",C,0)
mit den Argumenten an dieser Stelle auf. Dieser Aufruf gibt C
zurück, das zu perm
hinzugefügt wird.
Wir brechen die Schleife aus und prüfen, ob wir unerledigte Geschäfte haben. Somit haben wir an dieser Stelle unseren initial
als B
, und Wörter
haben ein Element, nämlich C
. Nun wiederholt sich die Schleife durch Hinzufügen von B
an verschiedenen Stellen mit C
. Somit erhalten wir BC
und CB
als zwei Elemente innerhalb der Set
-Wörter.
An diesem Punkt sind wir aus der Schleife und erhalten den initial
Wert als A
. Wir wiederholen diesen Vorgang weiter und fügen das Anfangszeichen A
an möglichen Stellen in unseren früheren Permutationen ein. Als erstes erhalten wir für BC
ABC
BAC
und BCA
. In ähnlicher Weise machen wir für die zweite Permutation CB
dasselbe: Fügen Sie den ersten Buchstaben an möglichen Positionen ein und erhalten Sie ACB
, CAB
und CBA
.
import java.util.HashSet;
import java.util.Set;
public class PermutationFinder {
public static Set<String> permutationFinder(String str) {
Set<String> perm = new HashSet<String>();
if (str == null) {
return null;
} else if (str.length() == 0) {
perm.add("");
return perm;
}
char initial = str.charAt(0);
String rem = str.substring(1);
Set<String> words = permutationFinder(rem);
for (String strNew : words) {
for (int i = 0; i <= strNew.length(); i++) {
perm.add(insertChar(strNew, initial, i));
}
}
return perm;
}
public static String insertChar(String str, char c, int j) {
String begin = str.substring(0, j);
String end = str.substring(j);
return begin + c + end;
}
public static void main(String args[]) {
String s1 = "ABC";
System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
}
}
Dies sind alle möglichen Permutationen der Zeichenkette “ABC”.
Ausgabe:
Permutations for ABC are:
[ACB, BCA, ABC, CBA, BAC, CAB]
Rupam Saini is an android developer, who also works sometimes as a web developer., He likes to read books and write about various things.
LinkedInVerwandter Artikel - Java String
- So führen Sie die Konvertierung von String in String-Array in Java durch
- Wie entferne ich eine Unterzeichenkette aus einer Zeichenkette in Java
- So konvertieren Sie Byte-Array in Hex-String in Java
- Wie man Java-String in Byte konvertiert
- Generieren Sie eine zufällige Zeichenkette in Java
- Die Swap-Methode in Java