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