Permutations of string in Java
Normally we're not supposed to answer questions containing broken code. But I actually found this one too interesting not to fix it.

A side effect of fixing the algorithm actually greatly simplified the method as well. This is what I ended up with:

private static void permutation(String prefix, String str) {
    for (int i = 0; i &lt; str.length(); i++) {
        String current = prefix+str.charAt(i);
        System.out.print(current+ " ");
        count++;
        permutation(current, str.substring(0, i) + str.substring(i + 1));
    }
}


The only thing wrong with the current implementation is the static count. What happens if you run the permutation method more than once? Perhaps on 2 different strings?

Let's make the count local to the method instead.

private static int permutation(String prefix, String str) {
    int count = 0;
    for (int i = 0; i &lt; str.length(); i++) {
        String current = prefix+str.charAt(i);
        System.out.print(current+ " ");
        count++;
        count += permutation(current, str.substring(0, i) + str.substring(i + 1));
    }
    return count;
}


I think this is simple enough that I don't need to explain how this works.



Now for your concern about removing the recursion.  

I don't think this is necessary. The only reason recursion in java is bad in general is that you add the method call to the stack each time, which might result in a stackoverflow.

Here the depth of the recursion is only equal to the length of the string. This will always be really low compared to the number of permutations that have to be calculated. For example: a string of length 10 would only go 10 recursions deep but has millions of permutations.



EDIT: implementation without string concatenations.

I had some more fun with this and tried to remove all string concatenations. Since we're only interested in printing the substrings, not necessarily return them we can optimise for this too.

All we need is a char[] to represent the string. The advantage is that we can really cheaply swap 2 letters in the string. Let's first create a helper function for swapping 2 letters in a string:

private static void swap(char[] string, int a, int b){
    if(a==b) return;
    char temp = string[a];
    string[a] = string[b];
    string[b] = temp;
}


I added the if(a==b) so we don't "swap" a letter with itself.

Let's also add another helper method to print out a single permutation. Since we pass the entire char[] we also need to add how many characters should be printed:

 private static void printUpTo(char[] string, int n){
    for (int i = 0; i &lt; n; i++) {
        System.out.print(string[i]);
    }
    System.out.print(" ");
}


Now that we have the helper functions the actual method implementation becomes relatively easy. The main idea is to keep track of what the current prefix is. This is just an int pointing to an index in the char[]. Then for each char after that index we do the same steps as before, but adapted to using the array:


append it to the current prefix => swap to the first spot after the prefix.
print the current word => print the first prefix + 1 characters
increment count
recursively call for new prefix and remaining letters => call with the array and prefix + 1
reverse the swap so we don't mess up further iterations.


The actual implementation looks like this:

private static int printPermutations(char[] string, int prefix){
    int count = 0;
    for(int i = prefix; i&lt; string.length; i++){
        swap(string, i, prefix);
        printUpTo(string, prefix+1);
        count ++;
        count += printPermutations(string, prefix + 1);
        swap(string, i, prefix);
    }
    return count;
}


It should be noted that since we swap the first letter after the prefix with the other letter, we lose the ordering. So for string "ABCD" this one doesn't print all permutations alphabetically, whereas the previous implementation did.

Fixing this is possible if we rotate instead of swapping. The implementation looks something like this:

private static int printPermutations(char[] string, int prefix) {
    int count = 0;
    for (int i = prefix; i &lt; string.length; i++) {
        rotate(string, prefix, i);
        printUpTo(string, prefix + 1);
        count++;
        count += printPermutations(string, prefix + 1);
        reverseRotate(string, prefix, i);
    }
    return count;
}

private static void rotate(char[] string, int a, int b) {
    if (a == b) {
        return;
    }
    char temp = string[b];
    System.arraycopy(string, a, string, a + 1, b - a);
    string[a] = temp;
}

private static void reverseRotate(char[] string, int a, int b) {
    if (a == b) {
        return;
    }
    char temp = string[a];
    System.arraycopy(string, a + 1, string, a, b - a);
    string[b] = temp;
}


But in my opinion, this isn't worth it. The first implementation was good enough.