Wayne Miller Anagram Problem Solver

Source Code:

//Solver for the Wayne Miller Anagram Problem defined as:
//   What is the longest sequence of letters for which all permutations are anagrams?
//   I can think of "on" and "no" which has length 2.
//   How far can you get if you allow foreign words, e.g. "is" and "si"?
//by B.J. Guillot, November 10, 2015

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Iterator;

public class Anagram {

	private static String DICTIONARY = "/usr/share/dict/words"; //Mac OS X
	private static int MAX_LETTERS = 16;
	private ArrayList<HashSet<String>> wordlist = new ArrayList<HashSet<String>>(MAX_LETTERS);

	public Anagram() {
		loadWordlist();
		for (int i=1; i < MAX_LETTERS; i++) { //skip length=1 words
			boolean found = false;
			Iterator<String> iter = wordlist.get(i).iterator();
			while (iter.hasNext()) {
				String s = iter.next();
				boolean allAnagramsAreWords = permutation("", s);
				if (allAnagramsAreWords)
					System.out.println(s);
			}
		}
	}

	private boolean permutation(String prefix, String str) {
		//adapted from http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html
		int n = str.length();
		if (n == 0) {
			//prefix is one of the computed anagrams
			if (!wordlist.get(prefix.length()-1).contains(prefix))
				return false;
		} else {
			for (int i = 0; i < n; i++) {
				boolean rc = permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
				if (!rc)
					return false;
			}
		}
		return true;
	}

	private void loadWordlist() {
		for (int i=0; i < MAX_LETTERS; i++)
			wordlist.add(new HashSet<String>());

		try {
			BufferedReader br = new BufferedReader(new FileReader(DICTIONARY));
			String s;
			while ((s = br.readLine()) != null) {
				if (s.length() <= MAX_LETTERS)
					wordlist.get(s.length()-1).add(s.toLowerCase());
			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		}		

		for (int i=0; i < MAX_LETTERS; i++)
			System.out.println(wordlist.get(i).size() + " dictionary words length=" + (i+1) + " loaded.");
	}

	public static void main(String[] args) {
		Anagram anagram = new Anagram();
	}

}

Output:
26 dictionary words length=1 loaded.
139 dictionary words length=2 loaded.
1294 dictionary words length=3 loaded.
4994 dictionary words length=4 loaded.
9972 dictionary words length=5 loaded.
17462 dictionary words length=6 loaded.
23713 dictionary words length=7 loaded.
29842 dictionary words length=8 loaded.
32286 dictionary words length=9 loaded.
30824 dictionary words length=10 loaded.
25963 dictionary words length=11 loaded.
20447 dictionary words length=12 loaded.
14923 dictionary words length=13 loaded.
9761 dictionary words length=14 loaded.
5922 dictionary words length=15 loaded.
3377 dictionary words length=16 loaded.
pu
ho
ya
ye
ym
id
if
aa
ab
ad
ae
in
ah
ak
is
al
it
am
an
ra
ar
as
at
re
aw
ay
ro
ba
sa
se
ka
si
so
ko
ta
la
ti
da
de
tu
di
do
ma
me
um
un
up
ea
ed
ut
mo
eh
em
mu
en
my
er
es
na
ey
ne
ni
no
fi
nu
fo
wa
od
of
og
wo
oh
ok
om
on
or
os
go
ow
ha
he
ree
ere
eer
Back