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