      1  import java.util.ArrayList;

      2

      3  /**

      4     This class generates permutations of a word.

      5  */

      6  public class PermutationGenerator

      7  {

      8     private String word;

      9

     10     /**

     11        Constructs a permutation generator.

     12        @param aWord the word to permute

     13     */

     14     public PermutationGenerator(String aWord)

     15     {

     16        word = aWord;

     17     }

     18

     19     /**

     20        Gets all permutations of a given word.

     21     */

     22     public ArrayList<String> getPermutations()

     23     {

     24        ArrayList<String> permutations = new ArrayList<String>();

     25

     26        // The empty string has a single permutation: itself

     27        if (word.length() == 0)

     28        {

     29           permutations.add(word);

     30           return permutations;

     31        }

     32

     33        // Loop through all character positions

     34        for (int i = 0; i < word.length(); i++)

     35        {

     36           // Form a simpler word by removing the ith character

     37           String shorterWord = word.substring(0, i)

     38                 + word.substring(i + 1);

     39

     40           // Generate all permutations of the simpler word

     41           PermutationGenerator shorterPermutationGenerator

     42                 = new PermutationGenerator(shorterWord);

     43           ArrayList<String> shorterWordPermutations

     44                 = shorterPermutationGenerator.getPermutations();

     45

     46           // Add the removed character to the front of

     47           // each permutation of the simpler word,

     48           for (String s : shorterWordPermutations)

     49           {

     50              permutations.add(word.charAt(i) + s);

     51           }

     52        }

     53        // Return all permutations

     54        return permutations;

     55     }

     56  }