文字列のすべての可能な順列を再帰的に計算するJava

Question

Javaで再帰を使用して、指定された文字列のすべての可能な順列を計算しようとしています。しかし、自分のコードに何が問題なのか分かりません。

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; 
} 

は、任意のヘルプをお願い申し上げ：

は、ここに私のアルゴリズムです。ありがとう！

Answer 1

いくつかの問題があります。

1. は、次の行：String sub = str.substring(i+1, str.length());はしばらく、同じラインもそのまま残っている部分文字列の「ブロック」としてインデックスi後に何を扱う最初の文字
2. を無視順列を生成するために、現在の（最初の）文字を文字列の残りの2文字の間に挿入する必要があります。各置換のためにそれを行います。
3. 行s = str.charAt(i) + s;は＃2で同じ誤りを繰り返す

は、ここで修正案です：私たちはどちらか間違っているのか分からない

---

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; 
}