Java Reference

In-Depth Information

PermutationGenerator
. Just know that by “enumerating” the permutations of

w
we mean returning them, one by one, as the result of calls to function
next-

Element
. Also, the rule must be followed that
nextElement
is called only if it is

guaranteed that another permutation of
w
exists to be enumerated.

Class
PermutationGenerator
is in Figs. 15.12. and 15.13.

Our basic idea for enumerating the permutations of a
String
like
"xyz"
is

first to enumerate the permutations that begin with
x
, then to enumerate the per-

mutations that begin with
"y"
, and then to enumerate the permutations that begin

with
"z"
. We will do this using the following fields.

Variable
word
contains the word whose permutations are being enumerated,

and
hasAnother
indicates whether all its permutations have been enumerated.

Variable
pos
contains the index of a character in
word
, and permutations

beginning with character
word[pos]
are being enumerated. Variable
subWord

then contains the characters of
word
but with character
word[pos]
removed.

Thus, we are in the process of constructing and enumerating:

word[pos] +
first permutation of
subWord

word[pos] +
second permutation of
subWord

…

word[pos] +
last permutation of
subWord

How do we construct these permutations of
subWord
? We use an instance of

PermutationGenerator
, whose name is stored in field
subEnum
. This is the

recursively constructed object.

At this point, turn to the beginning of Fig. 15.12 and read carefully the class

invariant, which describes the relation among the fields of the class.

Now, one can look at the constructor and see that it truthifies the represen-

tation invariant. Also, function
hasMoreElements
is easily seen to be correct.

Function
nextElement
is more complicated. First, if
word
is the empty

string, it sets
hasAnother
to indicate that there are no more permutations and

returns the empty string. If word is not the empty string, it first stores the next

permutation in variable
next
—the permutation is the character
word[pos]
cate-

nated with the next permutation of
subWord
. It then calls a private procedure

getReadyForNext
, which appears in Fig. 15.13. This procedure does what has

to be done to make the class invariant true after permutation
next
is returned.

Then, permutation
next
is returned. And that is it.

Generating permutations would be much harder if we did not use recursive

objects. With them, the task turns out to be relatively simple.

15.6

Key concepts

• Recursive definitions.
Recursive definitions play an important role in mathe-

matics and fields that use mathematics.

• Recursion methods and recursive objects.
In programming, recursion comes

Search WWH ::

Custom Search