Permutations.java.html

  1  import java.util.ArrayList;
  2  
  3  /**
  4     This program computes permutations of a string.
  5  */
  6  public class Permutations
  7  {
  8     public static void main(String[] args)
  9     {
 10        for (String s : permutations("eat"))
 11        {         
 12           System.out.println(s);
 13        }
 14     }
 15  
 16     /**
 17        Gets all permutations of a given word.
 18        @param word the string to permute
 19        @return a list of all permutations
 20     */
 21     public static ArrayList<String> permutations(String word)
 22     {
 23        ArrayList<String> result = new ArrayList<String>();
 24  
 25        // The empty string has a single permutation: itself
 26        if (word.length() == 0) 
 27        { 
 28           result.add(word); 
 29           return result; 
 30        }
 31        else
 32        {
 33           // Loop through all character positions
 34           for (int i = 0; i < word.length(); i++)
 35           {
 36              // Form a shorter word by removing the ith character
 37              String shorter = word.substring(0, i) + word.substring(i + 1);
 38  
 39              // Generate all permutations of the simpler word
 40              ArrayList<String> shorterPermutations = permutations(shorter);
 41  
 42              // Add the removed character to the front of
 43              // each permutation of the simpler word, 
 44              for (String s : shorterPermutations)
 45              {
 46                 result.add(word.charAt(i) + s);
 47              }
 48           }
 49           // Return all permutations
 50           return result;
 51        }
 52     }
 53  }
 54