Hoe alle permutaties van een String vinden in Java

In deze tutorial zullen we leren hoe we de permutatie van een String kunnen vinden in een Java-programma. Het is een lastige vraag en wordt meestal gesteld tijdens Java-interviews.

Algoritme voor permutatie van een String in Java

We zullen eerst het eerste karakter uit de String nemen en dit permuteren met de overgebleven tekens. Als String = “ABC” is het eerste karakter = A en de permutaties van de overgebleven tekens zijn BC en CB. Nu kunnen we het eerste karakter invoegen op de beschikbare posities in de permutaties. BC -> ABC, BAC, BCA CB -> ACB, CAB, CBA We kunnen een recursieve functie schrijven om de permutaties terug te geven en vervolgens nog een functie om de eerste karakters in te voegen om de volledige lijst van permutaties te krijgen.

Java-programma om permutaties van een String af te drukken

package com.journaldev.java.string;

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

/**
 * Java Program to find all permutations of a String
 * @author Pankaj
 *
 */
public class StringFindAllPermutations {
    public static Set permutationFinder(String str) {
        Set perm = new HashSet();
        //Behandeling van foutscenario's
        if (str == null) {
            return null;
        } else if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set 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("\nPermutations for " + s + " are: \n" + permutationFinder(s));
        System.out.println("\nPermutations for " + s1 + " are: \n" + permutationFinder(s1));
        System.out.println("\nPermutations for " + s2 + " are: \n" + permutationFinder(s2));
    }
}

I have used Set to store the string permutations. So that duplicates are removed automatically.

Output

Permutations for AAC are: 
[AAC, ACA, CAA]

Permutations for ABC are: 
[ACB, ABC, BCA, CBA, CAB, BAC]

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

Dat is alles voor het vinden van alle permutaties van een String in Java.

Je kunt het voorbeeldprogrammacode downloaden van onze GitHub-opslagplaats.