1.3.2 Printing Anagrams1.3.1 Printing a Number1.3 Recursion1.3.3 Drawing Fractals

1.3.2 Printing Anagrams

Suppose we want to list all the  anagrams of a specified word, i.e., all permutations for the letters of the word. For instance, the anagrams of "cat" are

cat, cta, act, atc, tac, tca.

One approach to determine all anagrams is the following. Assume that we have fixed the first s letters of the anagram and want to determine the remaining letters (initially s = 0). For instance, if the original word is "word" and the first letter of the anagram is fixed to "w", the anagrams that we want to compute are

word, wodr, wrod, wrdo, wdro, wdor

The recursive problem solution then proceeds as follows:

In the actual implementation, we use an array a of length n (the number of characters in the word) such that

Initially (when s=0), the array is initialized with the letters of the word. The corresponding Java method is

  // -------------------------------------------------------
  // printAnagrams(word)
  // print all anagrams of word
  //
  // Input:
  //   'word' is not null.
  // Effect:
  //   as explained above, 'word' remains unchanged.
  // -------------------------------------------------------
  static void printAnagrams(String word)
  {
    final int n = word.length();
    char a[] = new char[n];
    for (int i = 0; i < n; i++)
      a[i] = word.charAt(i);
    printAnagrams(a, 0, n);
  }

We fix a character for the next position s by taking one of the candidates from positions s to n-1 and exchanging it with the current character at s:

  // -------------------------------------------------------
  // printAnagrams(a, s, n)
  // print all anagrams of 'a' of length 'n' with first 's'
  // characters fixed
  //
  // Input:
  //   'a' is not null.
  //   'n' is length of 'a'.
  //   '0 <= s < n'.
  // Effect:
  //   as explained above, 'a' remains unchanged.
  // -------------------------------------------------------
  static void printAnagrams(char[] a, int s, int n)
  {
    if (s == n)
    {
        System.out.println(new String(a));
        return;
    }
  
    final char ch = a[s];
    for (int i = s; i < n; i++)
    {
        a[s] = a[i];
        a[i] = ch;
        printAnagrams(a, s+1, n);       
        a[i] = a[s];
    }
    a[s] = ch;
  }

In the base case of this recursive method we use the constructor

  String(char[] array)

we computes a string from a character array. In the recursive case, we save the character at position s in a temporary variable ch and exchange it with all candidate characters in turn. Finally, we restore the character in this position to ch such that the array remains unchanged after the call.

Please use the "cat" example above to study the behavior of printAnagrams.


© Wolfgang Schreiner; February 3, 2005

1.3.2 Printing Anagrams1.3.1 Printing a Number1.3 Recursion1.3.3 Drawing Fractals