Print all permutations of a given string in Java

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)?

• Is it ok that the string aa has two identical permutations? – Emanuele Paolini Aug 20 '14 at 12:31
• I assume that there are no repetitions in the characters. This can easily be fixed, is I use Set – user3371223 Aug 20 '14 at 12:33

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).

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.

• 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. – Simon Forsberg Aug 20 '14 at 12:41
• @SimonAndréForsberg Sure, but that's what Google masters. And someone else can show step-wise improvements. – maaartinus Aug 20 '14 at 12:44
• 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 ? – user3371223 Aug 20 '14 at 12:45
• @user3371223 Yes, what I've meant was the first code block in this answer. – maaartinus Aug 20 '14 at 12:48