GENERATING PERMUTATIONS

A permutation is an arrangement of elements in a linear order. For example, if the elements are the letters 'A', 'B', 'C' and 'D', we can generate the following 24 permutations:

ABCD BACD CABD DABC

ABDC BADC CADB DACB

ACBD BCAD CBAD DBAC

ACDB BCDA CBDA DBCA

ADBC BDAC CDAB DCAB

ADCB BDCA CDBA DCBA

In general, for n elements, there are n choices for the first element in a permutation. After the first element has been chosen, there are (n-1) choices for the second element. Continuing in this fashion, we see that the total numb er of permutations of n elements is

That is, there are n! different permutations of n elements.

We will develop a method to print all permutations of a String s. From the above example, where s = "ABCD", we can print out the permutations of s by printing:

the six permutations that start with 'A';

the six permutations that start with 'B';

the six permutations that start with 'C';

the six permutations that start with 'D'.

How can we accomplish the printing of the six permutations that start with 'A'? Look at the above list of permutations and try to figure out how to proceed. (Hint: 6 = 3!)

The key observation is that, for those six permutations, each one starts with 'A' and is followed by a different permutation of "BCD". This suggests a recursive solution. For each of the six permutations of "BCD", we write out all of s, and so we get the six permutations of "ABCD" that start with 'A'.

For the next six permutations, we first swap 'A' and 'B', so that s = "BACD". We then repeat the above process -- this time permuting "ACD" and printing out all of s for each permutation.

For the next six permutations, we start by swapping 'B' and 'C', so that s = "CABD". We then permute "ABD" and print s after each permutation.

For the last six permutations, we start by swapping 'C' and 'D' -- so that s = "DABC" -- and then print s after each permutation of "ABC".

As we did with cluster counting and the efficient, recursive Fibonacci function, we start with a wrapper method. Then the starting position for each level of permuting can be an argument to the recursive method. Also, Java strings are immutable, so to allow swapping of characters – and use of the index operator, [ ] – we copy s to an array of characters. To hide these implementation details from the user, the wrapper method has a single parameter, of type String:

// Postcondition: all the permutations of s have been printed.

public void permute (String s)
{
    recPermute (s.toCharArray( ), 0);

} // permute 

The postcondition for the recursive method, recPermute, is

// Postcondition: c has been printed for each permutation of 
//                c [k...c.length - 1].