Thinking Recursively with Java

Chapter 6. Permutations

The order is rapidly fading

And the first one now will later be last. . . .

—Bob Dylan, "The Times They Are A-Changin'," 1963

In Chapter 3, you learned how to count the number of permutations in a set. This chapter solves the problem of generating the actual permutations. Solving the more general problem makes use of the same recursive insights but requires thinking about permutations in a more sophisticated way.

Before turning to the problem of generating permutations, it helps to review the basic concept as it appeared in section 3.1, which introduced the term permutation to refer to an arrangement of objects in a linear order. If you begin with a collection of N distinct objects, there are N ways to choose the first item in the permutation, N−1 ways to choose the second, and so forth. This means that you can determine the total number of arrangements by computing

which is simply N!.

The goal of this chapter is to write a Java method listPermutations that will generate the complete set of permutations for any string of distinct characters. For example, given the string "ABCD", there are 24 (4!) different permutations, as follows:

To display these permutations of "ABCD", you would simply call

listPermutations("ABCD");

The format of the method call indicates ...