Calcul récursif de toutes les permutations possibles d'une chaîne Java

Question

J'essaie de calculer toutes les permutations possibles d'une chaîne donnée en utilisant la récursivité en Java. Cependant, je ne sais pas ce qui ne va pas avec mon code.

Voici mon algorithme:

public static ArrayList<String> computeAllPossiblePermutations(String str) 
{ 
    ArrayList<String> perms = new ArrayList<>(); 

    //base case 
    if (str.length() == 1) 
     perms.add(str); 

    else 
    { 
     //loop over the string 
     for (int i = 0; i < str.length() - 1; i++) 
     { 
      //make a subset of the string excluding the first char 
      String sub = str.substring(i+1, str.length()); 
      //compute permutations of the subset 
      ArrayList<String> subPerms = computeAllPossiblePermutations(sub); 
      //add the first char that we excluded at the start of each permutations 
      for (String s : subPerms) 
      { 
       s = str.charAt(i) + s; 
       perms.add(s); 
      } 
     } 

    } 

    return perms; 
} 

apprécierait toute aide. Merci!

Answer 1

Il y a quelques problèmes:

1. La ligne suivante: String sub = str.substring(i+1, str.length()); ne tient pas compte du premier caractère
2. La même ligne traite également quelque chose après l'indice i comme un « bloc » de sous-chaîne qui reste inchangé, alors que afin de générer des permutations nous devrions insérer le caractère courant (premier) entre les deux personnages du reste de la chaîne - et faire pour chaque permutation
3. la ligne s = str.charAt(i) + s; répète la même erreur dans # 2

Voici une solution suggérée:

---

public static ArrayList<String> computeAllPossiblePermutations(String str) { 
    ArrayList<String> perms = new ArrayList<>(); 
    if (str.length() == 1) { 
     perms.add(str); 
    } else { 
     String chr = str.substring(0,1); 
     String rest = str.substring(1); 
     ArrayList<String> subPerms = computeAllPossiblePermutations(rest); 
     for (String s : subPerms) { 
      for (int j = 0; j <= s.length(); j++) { 
       String newPerm = s.substring(0,j) + chr + s.substring(j); 
       perms.add(newPerm); 
      } 
     } 
    } 
    return perms; 
}