01: import java.util.ArrayList;
02: 
03: /**
04:    This class generates permutations of a word.
05: */
06: public class PermutationGenerator
07: {
08:    /**
09:       Constructs a permutation generator.
10:       @param aWord the word to permute
11:    */
12:    public PermutationGenerator(String aWord)
13:    {
14:       word = aWord;
15:    }
16: 
17:    /**
18:       Gets all permutations of a given word.
19:    */
20:    public ArrayList<String> getPermutations()
21:    {
22:       ArrayList<String> result = new ArrayList<String>();
23: 
24:       // The empty string has a single permutation: itself
25:       if (word.length() == 0) 
26:       { 
27:          result.add(word); 
28:          return result; 
29:       }
30: 
31:       // Loop through all character positions
32:       for (int i = 0; i < word.length(); i++)
33:       {
34:          // Form a simpler word by removing the ith character
35:          String shorterWord = word.substring(0, i)
36:                + word.substring(i + 1);
37: 
38:          // Generate all permutations of the simpler word
39:          PermutationGenerator shorterPermutationGenerator 
40:                = new PermutationGenerator(shorterWord);
41:          ArrayList<String> shorterWordPermutations 
42:                = shorterPermutationGenerator.getPermutations();
43: 
44:          // Add the removed character to the front of
45:          // each permutation of the simpler word, 
46:          for (String s : shorterWordPermutations)
47:          {
48:             result.add(word.charAt(i) + s);
49:          }
50:       }
51:       // Return all permutations
52:       return result;
53:    }
54: 
55:    private String word;
56: }