Wie man alle Permutationen eines Strings in Java findet

Einleitung

In diesem Tutorial lernen wir, wie man die Permutationen eines Strings in einem Java-Programm findet. Dieses Thema ist nicht nur anspruchsvoll, sondern bietet auch wertvolle Einblicke in die Programmierlogik. Permutationen sind wichtig, da sie in verschiedenen Szenarien wie Algorithmen und Kombinatorik eine Rolle spielen. Die Fähigkeit, Permutationen zu berechnen, zeigt zudem ein tiefes Verständnis für Datenstrukturen und rekursive Ansätze. Es ist eine anspruchsvolle Frage und wird oft in Java-Interviews gestellt, um die Problemlösungsfähigkeiten zu bewerten. Dieses Wissen kann zudem in realen Anwendungen wie Kryptografie, Passwortgeneratoren und mathematischen Modellen genutzt werden. Java bietet folglich leistungsstarke Tools, um solche Aufgaben effizient zu lösen.

Algorithmus zur Permutation eines Strings in Java

Zunächst nehmen wir das erste Zeichen des Strings und permutieren es mit den verbleibenden Zeichen.

Beispielsweise, wenn String = "ABC":

• Erstes Zeichen = A
• Permutationen der verbleibenden Zeichen = BC und CB

Nun können wir das erste Zeichen in die verfügbaren Positionen der Permutationen einfügen:

• BC -> ABC, BAC, BCA
• CB -> ACB, CAB, CBA

Wir können eine rekursive Funktion schreiben, um die Permutationen zurückzugeben, und eine weitere Funktion, um das erste Zeichen einzufügen, um die vollständige Liste der Permutationen zu erhalten.

Java-Programm zum Drucken der Permutationen eines Strings

package com.journaldev.java.string;

import java.util.HashSet;
import java.util.Set;

/**
 * Java-Programm, um alle Permutationen eines Strings zu finden
 * @author Pankaj
 */
public class StringFindAllPermutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        // Behandlung von Fehlerszenarien
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // Erstes Zeichen
        String rem = str.substring(1); // Vollständiger String ohne erstes Zeichen
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0; i <= strNew.length(); i++) {
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }

    public static String charInsert(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 s = "AAC";
        String s1 = "ABC";
        String s2 = "ABCD";
        System.out.println("\nPermutationen für " + s + " sind: \n" + permutationFinder(s));
        System.out.println("\nPermutationen für " + s1 + " sind: \n" + permutationFinder(s1));
        System.out.println("\nPermutationen für " + s2 + " sind: \n" + permutationFinder(s2));
    }
}
  

Ausgabe

Permutationen für AAC sind:

[AAC, ACA, CAA]

Permutationen für ABC sind:

[ACB, ABC, BCA, CBA, CAB, BAC]

Permutationen für ABCD sind:

[DABC, CADB, BCAD, DBAC, BACD, ABCD, ABDC, DCBA, ADBC, ADCB, CBDA, CBAD, DACB, ACBD, CDBA, CDAB, DCAB, ACDB, DBCA, BDAC, CABD, BADC, BCDA, BDCA]

Fazit

Ich habe Set verwendet, um die Permutationen des Strings zu speichern und sicherzustellen, dass Duplikate automatisch entfernt werden. Diese Methode erleichtert die Verwaltung von Ergebnissen und reduziert unnötige Berechnungen erheblich. Das Set ermöglicht zudem eine effiziente Speicherung und Verarbeitung von Daten, da es automatisch doppelte Einträge ignoriert. Die Verwendung eines Sets spart zudem Speicherplatz und sorgt für präzise Ergebnisse. Durch diese Vorgehensweise werden alle möglichen Permutationen eines Strings schnell und sicher generiert. Diese Technik ist besonders nützlich für Projekte mit eindeutigen Daten. Das war alles, um alle Permutationen eines Strings in Java zu finden. Probieren Sie den Algorithmus aus, um die Vorteile selbst zu erleben.