Permutations of a String.

One of the standard algorithms that has many applications is the permutation problem. Permutations of a string involves generating all possible arrangements of a String. In order to do so, we keep part of a string the same, while generating the possible arrangements of remaining string.

  Given a string ABCD, in order to generate all the permutations,
1. Fix the position of A and permute rest of the String BCD. Now for the String BCD, we fix the position of B and generate permutations for CD.(1a) Next we swap B & C in BCD and fix the position of C, generate the permutations for BD. (1b)
Finally we swap B&D in BCD and fix the position of D, generate the permutations for BC. (1c). This completes the permutations for BCD.
2. Now we swap B with A in ABCD, fix the position of B and generate the permutations for ACD. (2a, 2b, 2c)

Similarly we swap C and D with A and generate permutations for BAD(3a, 3b, 3c) and BCA(4a, 4b, 4c).

At every step, we are performing the same operations swap and permute substring on a smaller data set. So we can implement a recursive solution.


Here's the recursive solution in java.

void permute(int read, int write, String[] input, String[] output) {
    if(write == output.length) {
        printPermutation(output);
        return;
    }
    for(int i = read; i < input.length; i++) {
        swap(i, read);
        output[write] = input[read];
        permute(read + 1, write + 1, input, output);
        swap(i, read);
    }
}

In every recursive call, we move the ith element of input array to current position and fix the current position. We copy this element to the output array. Then we process the remaining string(recursive call) and swap the ith element back to its position. When the output array is full, we print the array and start again.
For example, for a string ABCD and read = 0 & i = 0, we swap A with A, write A to output array and make a recursive call to process the remaining string ABC - permute(1,1,[A,B,C,D],[A]).



Below recursion tree helps in understanding the recursive code.