Java Reference
In-Depth Information
import
java.util.*;
/**
An instance produces permutations of a string
*/
public class
PermutationGenerator
implements
Enumeration {
/*
class invariant:
(1)
The definitions of
word
,
hasAnother
, and
pos
hold
(2)
In the case that word
!= "":
(a) Definitions of
subWord
and
subEnum
hold
(b) Permutations of
word
that begin with a letter in
word[0..pos-1]
have
been generated.
(c) All permutations of the form
word[pos] + e
where
e
was enumerated by
subEnum
have been enumerated
(d) If
pos < word.length, e
has another permutation to enumerate
*/
private
String word; //
The word whose permutations are being enumerated
private boolean
hasAnother=
true
; // = "
there is another permutation to enumerate"
//
if
word
is not
""
, then we use these variables:
private int
pos; // 0 <= pos <= word.length
private
String subWord; // word
but with character
word[pos]
removed
private
PermutationGenerator subEnum; //
An enumeration for
subWord
//
Constructor: an enumeration for
w
public
PermutationGenerator(String w) {
word= w; pos= 0;
if
(word.length() != 0) {
subWord= word.substring(1);
subEnum=
new
PermutationGenerator(subWord);
}
}
/** =
this enumeration has another element
*/
public boolean
hasMoreElements()
{
return
hasAnother; }
/** =
the next permutation of this enumeration
*/
public
Object nextElement() {
if
(word.equals("")) {
hasAnother=
false
;
return
"";
}
String next= word.charAt(pos) + (String) subEnum.nextElement();
getReadyForNext();
return
next;
}
Figure 15.12:
Class
PermutationGenerator
(see also Fig. 15.13)
Search WWH ::
Custom Search