1
\$\begingroup\$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.