Comment trouver toutes les permutations d’une chaîne en Java

Dans ce tutoriel, nous apprendrons comment trouver la permutation d’une chaîne dans un programme Java. C’est une question délicate souvent posée lors d’entretiens en Java.

Algorithme de permutation d’une chaîne en Java

Nous prendrons d’abord le premier caractère de la chaîne et le permuterons avec les caractères restants. Si la chaîne est « ABC », le premier caractère est A et les permutations des caractères restants sont BC et CB. Maintenant, nous pouvons insérer le premier caractère dans les positions disponibles dans les permutations. BC -> ABC, BAC, BCA CB -> ACB, CAB, CBA Nous pouvons écrire une fonction récursive pour retourner les permutations, puis une autre fonction pour insérer les premiers caractères et obtenir la liste complète des permutations.

Programme Java pour imprimer les permutations d’une chaîne

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();
        //Gestion des scénarios d'erreur
        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.

Sortie

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]

C’est tout pour trouver toutes les permutations d’une chaîne en Java.

Vous pouvez télécharger le code du programme exemple depuis notre Dépôt GitHub.