In this lab we will develop a recursive method to print all permutations of a string. Along the way, we will see another example of a wrapper method.

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 number of permutations of n elements is

That is, there are n! different permutations of n distinct 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 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:

  /**
   * Finds all permutations of a specified String.
   *
   * @param s - the String to be permuted.
   *
   * @return a String representation of all the permutations.
   **/
  public static String permute (String s)

  /**
   * Finds all permutations of a subarray from a given position to the end of the array.
   *
   * @param c - an array of characters
   * @param k - the starting position in c of the subarray to be permuted.
   *
   * @return a String representation of all the permutations.
   **/