Recursion Examples in Java - Anagrams

Anagrams

An anagram is a word or phrase formed by re-arranging the letters of a different word or phrase, using all the original letters exactly once. For example, “coronavirus” = “carnivorous”.

In this chapter, we’ll look at the problem of listing all the rearrangements of a word entered by the user. For example, if the user types east, the program should list all 24 permutations, including eats, etas, teas, and non-words like tsae. If we want the program to work with any length of word, there is no straightforward way of performing this task without recursion.

With recursion, though, we can do it by thinking through the magical assumption. If we had a four-letter word, our magical assumption allows us to presume our recursive method knows how to handle all words with fewer than four letters. So what we might hope to do is to take each letter of the four-letter word, and place that letter at the front of all the three-letter permutations of the remaining letters. Given east, we would place e in front of all six permutations of ast — ast, ats, sat, sta, tas, and tsa — to arrive at east, eats, esat, esta, etas, and etsa. Then we would place a in front of all six permutations of est, then s in front of all six permutations of eat, and finally t in front of all six permutations of eas. Thus, there will be four recursive calls to display all permutations of a four-letter word.

Of course, when we’re going through the anagrams of ast, we would follow the same procedure. We first display an a in front of each anagram of st, then an s in front of each anagram of at, and finally a t in front of each anagram of as. As we display each of these anagrams of ast, we want to display the letter e before it.

To translate this concept into Java code, our recursive method will need two parameters. The more obvious parameter will be the word whose anagrams to display, but we also need the letters that we want to print before each of those anagrams. At the top level of the recursion, we may want to print all anagrams of east, without printing any letters before each anagram. But in the next level, one recursive call will be to to display all anagrams of ast, prefixing each with the letter e. And in the next level below that, one recursive call will be to display all anagrams of st, prefixing each with the letters ea.

The base case of our recursion would be when we reach a word with just one letter. Then, we just display the prefix followed by the one letter in question.

public class Anagrams extends Program {
    public void run() {
        String word = readLine("Give a word to anagram: ");
        printAnagrams("", word);
    }

    public void printAnagrams(String prefix, String word) {
        if(word.length() <= 1) {
            println(prefix + word);
        } else {
            for(int i = 0; i < word.length(); i++) {
                String cur = word.substring(i, i + 1);
                String before = word.substring(0, i); // letters before cur
                String after = word.substring(i + 1); // letters after cur
                printAnagrams(prefix + cur, before + after);
            }
        }
    }
}