String Permutations

The example in this section provides a more in-depth walkthrough of how to solve a recursive problem, especially one that does not involve a simple mathematical formula. The problem we analyze in this section is creating the permutations of a string of textall the different strings that can be created by rearranging the characters of the original string. Words created from these strings are known as anagrams. The permutations for the string "abc" are:

 abc
 acb
 bac
 bca
 cab
 cba

Such a program could come in handy if one wants to unscramble a string of characters, determine all the words that can be created from a string, or determine all the words that can be created from the characters associated with a telephone number.

We have already provided a few recursive solutions in this chapter, but we have not considered the flow of thought that results in a recursive solution. We do this now, in the context of string permutations. To begin, we look for a pattern that can be used to solve the problem. In the preceding list of permutations, note that two of the resulting permutations start with "a" ("abc" and "acb"), two with "b" ("bac" and "bca"), and two with "c" ("cab", "cba"). For each letter, permutations are provided that begin with that letter, followed by permutations of the remaining letters. If we were to begin with the letter "b", for example, we would have two permutations"bac" and "bca". These are determined by simply looking at the remaining two letters, "a" and "c", and seeing that there are only two permutations using these lettersnamely, "ac" and "ca". Note that we have now just determined all the permutations on the smaller string, "ac". To do this, we can use the same thought process as before, namely, determining all the permutations that start with the letter "a" followed by all the permutations that start with the letter "c". If we start with the letter "a", we have only one letter left, the letter "c". For a string with only one character, the string itself is the only permutation.

We now have the permutations of our substrings, but not the final permutations as shown above. To create these, we need to precede the permutations of the substrings with the characters that were removed to create the substring. For example, when determining the permutations of "bac", we divided the string into two strings ("b" and "ac"), and determined the permutations of the second string (in this case, "ac" and "ca"). We need our solution to precede "ac" and "ca" with the character that was removed to create this substring (namely, "b"). Our solution will need a way to keep track of these removed letters.

We have now found a way to break up our problem into two pieces: a single character from the original string, concatenated with all the permutations of the remaining charactersthe recursion step calculates all such permutations. The recursion step includes a recursive call for each letter in the string, with a different letter being used as the first letter of the permutation. Each call takes a different character from the string being permuted, and creates a substring of the remaining values, to be passed to the recursive call. For instance, if we are using the example of "abc", the first call to our recursive method results in three recursive callsone which determines all the permutations that begin with "a" (where the substring is "bc"), one which determines all the permutations that begin with "b" (where the substring is "ac") and one which determines all the permutations that begin with "c" (where the substring is "ab").

We have now discovered the recursion step for our program (determining the permutations of the various substrings) and our base case (a string with one letter will always have only one permutation, the letter itself). The next step is to ensure that the base case will be reached. Because our recursion step always calls with a string that is one character shorter than the string before it, we can be sure that we will always reach a string of one characterthe base case. Note that the base case also handles the situation where the user enters an empty string (i.e., one whose length is 0).

Now that we have determined our base case, the recursion step and that the base case will always be reached, we present the code for our solution (Fig. 15.12). Method permuteString (lines 738) takes two arguments. The first, beginningString, contains the characters that were removed from the string in previous calls and now need to precede the permutations that are being created. The second argument, endingString, contains the string that needs to be permuted (we call it endingString because for our final results it will be displayed after beginningString). When the method is called with the original string, the first argument will be the empty string, as there are no characters from previous calls that need to be added to the solution. The base case occurs in lines 1213, when the string being permuted contains only one character. In this case, we simply print the characters from previous calls (beginningString) followed by the character in endingString.

Figure 15.12. String permutations generated with a recursive method.

 1 // Fig. 15.12: Permutation.java
 2 // Recursive method to find all permutations of a String.
 3
 4 public class Permutation
 5 {
 6 // recursive declaration of method permuteString
 7 private void permuteString(
 8 String beginningString, String endingString )
 9 {
10 // base case: if string to permute is length less than or equal to
11 // 1, just display this string concatenated with beginningString
12 if ( endingString.length() <= 1 )
13 System.out.println( beginningString + endingString );
14 else // recursion step: permute endingString
15 {
16 // for each character in endingString
17 for ( int i = 0; i < endingString.length(); i++ )
18 {
19 try
20 {
21 // create new string to permute by eliminating the
22 // character at index i
23 String newString = endingString.substring( 0, i ) +
24  endingString.substring( i + 1 ); 
25
26 // recursive call with a new string to permute
27 // and a beginning string to concatenate, which
28 // includes the character at index i
29 permuteString( beginningString + 
30  endingString.charAt( i ), newString );
31 } // end try
32 catch ( StringIndexOutOfBoundsException exception )
33 {
34 exception.printStackTrace();
35 } // end catch
36 } // end for
37 } // end else
38 } // end method permuteString
39 } // end class Permutation

The recursion step occurs in lines 1437. The for statement makes a recursive call for each of the substrings. The current character being removed is the character returned from endingString.charAt( i ). Method charAt takes an integer argument and returns the character in the String at that index. As with arrays, the first element of a string is considered to be at position 0. The for statement iterates through each character in endingString, so that permutations will be created that begin with each letter in endingString.

To create the substring that needs to be permuted, the character at index i needs to be removed from the string that will be passed in the recursive call. To remove a character, we concatenate two substringsthe first substring contains all the characters that occur before the character being removed, and the second substring contains the portion of the string that occurs after the character being removed. For instance, to remove the character "s" from the word "recursion," we create the new string by concatenating the first substring, "recur", with "ion", resulting in "recurion." Lines 2324 create this substring using String method substring. Class String provides two substring methods to return a new String object created by copying part of an existing String object. The call in line 23 passes method substring two integers (0 and i). The first argument specifies the starting index in the original string from which characters are copied. The second argument specifies the index one beyond the last character to be copied (i.e., copy up to, but not including, that index in the string). The substring returned contains copies of the specified range of characters from the original string. Therefore, the method call in line 23 returns all the characters from the beginning of endingString up to, but not including, the character at index i (the character we are trying to remove). If the arguments are outside the bounds of the string, the program generates a StringIndexOutOfBoundsException (handled in lines 3235).

The method call in line 24 uses the substring method that takes one integer argument (i + 1), which specifies the starting index in the original string from which characters are to be copied. The substring returned contains a copy of the characters from the starting index to the end of the string. Therefore, the method call in line 24 returns all the characters that occur after the character we are trying to remove. If the argument is outside the bounds of the string, the program generates a StringIndexOutOfBoundsException (also handled in lines 3235).

Lines 2930 perform the recursive call. The first argument passed is beginningString concatenated with endingString.charAt( i ). This way we combine the characters isolated from previous calls (beginningString) with the character being isolated in this call. The second argument is newString, which is the substring to be permuted.

Figure 15.13 tests our recursive method. Line 9 creates a Scanner object to read a string in from the keyboard. Line 10 creates a Permutation object with which to call method permuteString. The string is read in at line 13 and passed to method permuteString in line 16. Note that this call provides an empty string as the first argument and the string to permute as the second argument. Because we have not yet removed any characters from the string, beginningString (the first argument) should be an empty string. Some programmers may want to define method permuteString as private, and create another public method that takes only the string to permute. This method could then call permuteString with the empty string as the first argument and the string to permute as the second argument. This would ensure that the user does not enter something other than the empty string as the first argument to method permuteString.

Figure 15.13. Testing the recursive method for permutations.

(This item is displayed on page 760 in the print version)

 1 // Fig. 15.13: PermutationTest.java
 2 // Testing the recursive method to permute strings.
 3 import java.util.Scanner;
 4
 5 public class PermutationTest
 6 {
 7 public static void main( String args[] )
 8 {
 9 Scanner scanner = new Scanner( System.in );
10 Permutation permutationObject = new Permutation();
11
12 System.out.print( "Enter a string: " );
13 String input = scanner.nextLine(); // retrieve String to permute
14
15 // permute String
16 permutationObject.permuteString( "", input );
17 } // end main
18 } // end class PermutationTest

 

math
maht
mtah
mtha
mhat
mhta
amth
amht
atmh
athm
ahmt
ahtm
tmah
tmha
tamh
tahm
thma
tham
hmat
hmta
hamt
hatm
htma
htam

 

The permutations will be printed to the command prompt. Note that if a string is entered with repeated characters (e.g., "hello"), each character is treated on its own, resulting in repeated permutations. One way to handle this problem is to store permutations as they are createdwhen each new permutation is formed, check the previously created strings and add the new string only if it has not already appeared. Finally, note from the output that there are 24 permutations for the string "math". The number of unique permutations for a string with n unique characters is equal to the factorial of n (i.e., there are four characters in "math", resulting in 4! permutations, or 24 permutations).