Permutations of string in Java This is a program about finding all the permutations of an string. I want to be able to make it faster and more efficient like eliminating the recursion maybe. Please advise.

What is intended is to also find the permutations of the sub-strings of the main string while repetitions should be omitted.

public class StrPerm {
    static int count = 0;

    public static void main(String[] args) {
        String str = "ABCD";
        permutation("", str);
        System.out.println("Total permutations of given string are : " + count);
    }

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


The results are as follows:


  A
  AB
  ABC
  ABCD
  AB
  ABD
  ABDC
  A
  AC
  ACB
  ACBD
  AC
  ACD
  ACDB
  A
  AD
  ADB
  ADBC
  AD
  ADC
  ADCB
  B
  BA
  BAC
  BACD
  BA
  BAD
  BADC
  B
  BC
  BCA
  BCAD
  BC
  BCD
  BCDA
  B
  BD
  BDA
  BDAC
  BD
  BDC
  BDCA
  C
  CA
  CAB
  CABD
  CA
  CAD
  CADB
  C
  CB
  CBA
  CBAD
  CB
  CBD
  CBDA
  C
  CD
  CDA
  CDAB
  CD
  CDB
  CDBA
  D
  DA
  DAB
  DABC
  DA
  DAC
  DACB
  D
  DB
  DBA
  DBAC
  DB
  DBC
  DBCA
  D
  DC
  DCA
  DCAB
  DC
  DCB
  DCBA
  
  Total permutations of given strings are : 84
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.