Trouver toutes les permutations d'une chaîne donnée en Java

La permutation est la technique mathématique pour déterminer le nombre d’arrangements possibles dans un ensemble lorsque l’ordre de l’arrangement compte.

Permutations d’une chaîne à l’aide de la récursivité

La fonction permutationFinder(String str) est récursive qui imprime chaque permutation de la chaîne passée. La variable Set est utilisée pour stocker les permutations d’une chaîne Java afin que les doublons soient supprimés automatiquement. Nous coupons nos mots, en prenant une lettre à la fois dans notre chaîne, et traitons les lettres restantes séparément.

La fonction insertChar insère le premier caractère pour obtenir la liste complète des permutations pour la chaîne que nous avons passée.

Nous commençons par la chaîne “ABC”, nous la parcourons, une lettre à la fois. Nous séparons notre caractère initial, A, et les autres sont BC. Maintenant, nous parcourons le rem et trouvons les permutations pour les lettres restantes. Le processus est expliqué plus en détail ci-dessous.

La fonction permutationFinder() est lancée jusqu’à ce que nous n’ayons plus rien à couper ; c’est pourquoi nous obtenons rem = "". À ce stade, nous ajoutons "" à perms et le renvoyons, qui est ensuite stocké dans la variable Set, words. Aussi, rappelez-vous que notre caractère initial à ce moment est C.

Nous bouclons chaque chaîne dans les mots Set. Nous avons strNew comme chaîne vide "", elle descend jusqu’à la deuxième boucle for dans ce cas, nous avons i=0 qui est égal à strNew.length() ; ainsi, nous appelons la méthode insertChar("",C,0) avec les arguments à ce point. Cet appel renvoie C, qui est ajouté dans perm.

Nous ouvrons la boucle et vérifions si nous avons des affaires inachevées. Ainsi, à ce stade, nous avons notre valeur initial comme B, et les mots ont un élément, qui est C. Maintenant, la boucle se répète en ajoutant B à différentes positions avec C. Ainsi, nous obtenons BC et CB comme deux éléments à l’intérieur des mots Set.

À ce stade, nous sommes hors de la boucle et obtenons la valeur initial comme A. Nous répétons encore ce processus et insérons le caractère initial A aux positions possibles dans nos permutations précédentes. Premièrement, pour BC, nous obtenons ABC BAC et BCA. De même, pour la deuxième permutation, CB, nous faisons la même chose : insérez la première lettre aux positions possibles et obtenez ACB, CAB et 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));
  }
}

Ce sont toutes les permutations possibles de la chaîne “ABC”.

Production:

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