//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();
}
}