Print all permutations of a given string in Java

Question

I want to print all permutations of a given string in Java. To do this I create one auxiliary array boolean used[] to check if I have used some character or not.

private static void permute(String s) {
 int n = s.length();
 boolean[] used = new boolean[n];
 char[] in = s.toCharArray();
 StringBuffer output = new StringBuffer();
 doPermute(in, output, used, n, 0);
 }
//helper method
private static void doPermute(char[] in, StringBuffer output,
 boolean[] used, int n, int level) {
 // TODO Auto-generated method stub
 if(n == level){
 System.out.println(output.toString());
 return;
 }
 for (int i = 0; i < in.length; i++) {
 if(used[i])
 continue;
 output.append(in[i]);
 used[i] = true;
 doPermute(in, output, used, n, level+1);
 used[i] = false;
 output.setLength(output.length()-1);
 }
 }
//main() method
public static void main(String[] args) {
 String s = "dog";
 permute(s);
 }

My main question: is there more elegant/better solution? Can I avoid using this auxiliary array (I tried to but it didn't work)?

• Emanuele Paolini: Is it ok that the string aa has two identical permutations?
• user3371223: I assume that there are no repetitions in the characters. This can easily be fixed, is I use Set

Answer 1

I'd bet you're right with used being somehow strange. The standard algorithm I recall doesn't need it. As I tried to improve your code, I ended up with the standard algorithm, so it's pointless to paste it here (someone else will surely do this better).

So some unsolicited general advice instead(*):

When you start with a main, call a static method, which uses another static method, then you're programming purely procedurally. I always recommend to stop it ASAP, e.g., by something like

public static void main(String[] args) {
 new MyClass().go(args);
}

Then you need no more static and can start putting some fields into your first object.

The other thing is printing instead of doing some reusable work.

---

(*) I consider this more important the good algorithmization as it took me long to grasp.

• Simon Forsberg: As I tried to improve your code, I ended up with the standard algorithm, so it's pointless to paste it here I would guess that the OP is not entirely aware of what "the standard algorithm" is in this case.
• maaartinus: @SimonAndréForsberg Sure, but that's what Google masters. And someone else can show step-wise improvements.
• user3371223: Thank you very much for the feedback! Yes, unfortunately I am not aware of the standard algorithm - is it this one: stackoverflow.com/questions/2920315/permutation-of-array ?
• maaartinus: @user3371223 Yes, what I've meant was the first code block in this answer.