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

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.