How to make permutation program using StringBuilder in java?

Question

I am willing to create a program that outputs all the possible permutations of a string. For example:

Input abc

Output

abc
acb
bac
bca
cab
cba

I am able to get this output when I use String in java, but I am curious do the same using StringBuilder in java.

I used the following code to do get this output.

public class Test {
    public static void permutations(String str, String ans) {
        if (str.length() == 0) {
            System.out.println(ans);
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            String newStr = str;
            newStr = newStr.substring(0, i) + newStr.substring(i + 1);
            permutations(newStr, ans + str.charAt(i));
        }
    }

    public static void main(String[] args) {        
            permutations("abc", ""); // using String
    }
}

I tried to create a similar method that resembles in structure with my permutation method and takes StringBuilder as parameter and work for it, but I am unable to do so, it shows me StringIndexOutOfBound Exception etc.

I am sharing the method I built below.

    public static void permutationsStringBuilder(StringBuilder str, StringBuilder ans) {
        if (str.length() == 0) {
            System.out.println(ans);
            return;
        }
        StringBuilder newstr = new StringBuilder(str);
        for (int i = 0; i < str.length(); i++) {
            try {
                ans.append(str.charAt(i));
                newstr.deleteCharAt(i);
                permutationsStringBuilder(newstr, ans);
                ans.deleteCharAt(i);
                newstr.replace(i, i, ""+str.charAt(i));
            } catch (StringIndexOutOfBoundsException e) {
            }
        }
    }

Output this is returning is:

abc
ccb
bac
cca

Please help me with this. Assist me make it work using StringBuilder of Java.

Answer 1

After the recursive call, you need to reset each StringBuilder to its original state before the loop iteration.

• One character was appended to ans, the last character should be removed.
• The ith character of newstr was removed, so it should be added back at the correct position.

ans.append(str.charAt(i));
newstr.deleteCharAt(i);
permutationsStringBuilder(newstr, ans);
ans.deleteCharAt(ans.length() - 1);
newstr.insert(i, str.charAt(i));