Finde alle Permutationen eines gegebenen Strings in Java

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]