find all permutations of a string

Question

I have been trying to understand how this works, but due to my limited knowldge of java, I fail to. Here is the code which will produce permutations:

private static void permutation(String prefix, String str) {
    int n = str.length();

    if (n == 0) System.out.println(prefix);

    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

//main:

public static void main(String[] args) {
        permutation("","ab");
    }

I tried to look at many stackoverflow posts but they dont go over the basics on how this works

Answer 1

The idea of this method is to use recursion to find all the permutations of a string. In order for recursion to work, it has to define the problem in terms of the same problem, slightly reduced.

What are the permutations of a string? Let's look at an example for the string "abc":

abc
acb
bac
bca
cab
cba

What we note about this is that the permutation is like picking one of the letters to be first, and then doing the same thing for the rest. That is, if we pick 'a' to be first, we have the permutations:

bc
cb

If we pick 'b' to be first, we have

ac
ca

And if we pick 'c', we have

ab
ba

So we can define our problem in terms of itself (reduced). So to permute a string that has n characters, we need to pick each of these characters, decide that it is the first, and then attach all the permutations of the remaining string to this first letter. This means we have to find all the permutations of a string that is n-1 characters long, and append it to the first letter we chose.

So,

• To find the permutations of an n-character string:
• Loop through all the characters of the string
  • Pick the current character we're looking at as the first character
  • Get all the remaining characters as a string (the length is now n-1)
  • Find all the (n-1)-character string's permutations
  • Append each of them to the character we picked as first.

But when do we stop? We stop when we get to an empty string, because it has no permutations.

What your program does is exactly this, but since it wants just to print the permutations, not to collect them, what it does is keep all the choices of first letters done in upper levels of the recursion. These are handed over from the upper levels of the recursion. This way, when we get down to an empty string, the prefix contains a particular series of choices of first letters. Since there is nothing more to permute, we can just print what we got.

When we return from the recursion at any level, the current level knows that all the permutations with the current choice of first character have been printed. So it moves to the next first character, and again, passes all the choices so far down. Again, all the levels under it will add their first letters until the string is empty.

At the top level you have to call it with an empty prefix, because of course, you haven't made any first character choices at this point. Let's see what happens if we call permutation("","abc"):

• Level 1 picks a, calls permutation("a","bc")
  • Level 2 picks b, calls permutation( "ab","c")
    • Level 3 picks c, calls permutation( "abc", "" )
      • Level 4 has an empty string, so it prints abc
    • Level 3 has nothing more to choose.
  • Level 2 picks c, calls permutation( "ac", "b")
    • Level 3 picks b, calls permutation( "acb", "" )
      • Level 4 has an empty string, so it prints acb
    • Level 3 has nothing more to choose
  • Level 2 has nothing more to choose
• Level 1 picks b, calls permutation("b","ac")
  • Level 2 picks a, calls permutation("ba","c")
    • Level 3 picks c, calls permutation( "bac", "" )
      • Level 4 has an empty string, so it prints bac
    • Level 3 has nothing more to choose
  • Level 2 picks c, calls permutation("bc","a")
    • Level 3 picks a, calls permutation( "bca", "" )
      • Level 4 has an empty string, so it prints bca
    • Level 3 has nothing more to choose
  • Level 2 has nothing more to choose
• Level 1 picks c, calls permutation("c","ab")
  • Level 2 picks a, calls permutation("ca","b")
    • Level 3 picks b, calls permutation( "cab", "" )
      • Level 4 has an empty string, so it prints cab
    • Level 3 has nothing more to choose
  • Level 2 picks b, calls permutation("cb","a")
    • Level 3 picks a, calls permutation( "cba", "" )
      • Level 4 has an empty string, so it prints cba
    • Level 3 has nothing more to choose
  • Level 2 has nothing more to choose
• Level 1 has nothing more to choose

Answer 2

The idea is pretty simple.

1. permutation will print each of the permutations of str preceded by prefix.
2. If str is empty, the only thing to print is prefix itself.
3. If it isn't empty, then we can break the problem up into a set of subproblems, each with a slightly longer prefix & shorter str by moving a different character form str to the end of prefix, and printing all of the permutations of each of these combinations. (Since we stop the recursion when str is empty, this gets us closer to that happening.)

Note that, if there are any duplicate characters, there will be duplicates in the result.

Answer 3

permutation is a recursive function, which means that it is a method that calls itself. Because we don't want the method to run forever in a continuous loop, we need to provide a base case which means a condition that causes the method to exit without calling itself. These methods are easier to understand by just following along with sample values. For instance, if we try permutation("", "a"), the code will run in this order (n is the length of str):

permutation("", "a")// n=1 so loop through "a" 
==>permution("a", "")// n=0 so print prefix "a" and exit

Now try permutation("", "ab"), we will have:

permutation("", "ab")// n=2 so loop through "ab"
==>permutation("a", "b")// n=1 so loop through "b"
====>permution("ab", "")// n=0 print prefix "ab" and exit
==>permutation("b", "a")// n=1 so loop through "a"
====>permution("ba", "")// n=0 print prefix "ba" and exit