How do I create a recursive anagram tool which prints every possible combination of a string of letters, including prefixes?

Question

I've made an anagram method to create all the possible combinations of a word, but I'd like to be able to check every letter combination.

For example: eastern would produce other variations such as earnest, but I'd also like it to produce variations such as east and eat and ate.

I already have a working dictionary checking whether the combinations are in the dictionary.

public void printAnagrams(String prefix, String word)
{
    if(word.length() == 1) {
        if (words.contains(prefix+word))
            System.out.println(prefix + word);
    }
    else    
    {
        for(int i = 0; i < word.length(); i++)
        {
            String current = word.substring(i, i + 1);
            String before = word.substring(0, i);
            String after = word.substring(i+1);
            printAnagrams(prefix + current, before + after);
        }
    }
}

A quick google search (Java print all combinations) found numerous Java solutions to this problem. In particular, the first result was just 2 functions, total of 5 or 6 lines of code, that does exactly what you need. — Tony, Mar 02 '12 at 17:33

amit · Accepted Answer · 2012-03-02T17:36:42.817

Have a set of chars [can be a char[]] and "guess" which is the next letter, and append it to an intermediate sol StringBuilder, which holds the current substring. Invoke the algorithm recursively to find out next chars of the solution.

Have an index i to indicate which chars can be used [all chars "right" to i].

At each iteration - print the resulting string, even if you did not the maximal length.

Pseudo code:

findPermutations(chars,i,sol):
   print sol
   if (chars.length == i):
       return
   for each j in range(j,chars.length):
       sol.append(chars[i+1])
       swap(chars,i,j) //we cannot use chars[j] anymore.
       findPermutations(chars,j+1,sol)
       swap(chars,i,j) //clean up environment
       sol.removeLast()

Notes:

This solution assumes chars is a set, so if a certain char appears more then once - you are going to have duplicates, but it will still work [generate all possibilities]
A word about complexity: There are exponential number of possibilities, and you want all of them. So, if you try to invoke this method [and actually any algorithm to do it] with more then 20 chars, you are expected to finish generating all possibilities in ~200 years

How do I create a recursive anagram tool which prints every possible combination of a string of letters, including prefixes?

1 Answers1