EDIT
This is a 'nice' problem, it ties in all the favourite educational problems, factorial, combinations, and permutations...
Here is working code that runs through the process.... I have commented it where I think necessary. I am doing this so that I have a record on here of what things are, and can refer back to it later, if needed.:
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.TreeSet;
public class Words {
/**
* Calculate all possible ways to permute data sets of up to 'max' values...
* <p>
* The result is a multi-dimensional array, with result[2] being the ways to
* permute 2-sized data sets ([1,2],[2,1]), and result[3] the way to permute 3-sized sets:
* ([1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]),
* etc.
*
* @param max the largest set to calculate permutations for.
* @return the possible ways to permute sets of values up to max values in size
*/
private static final int[][][] permutations(int max) {
int[][][] ret = new int[max + 1][][];
ret[0] = new int[0][];
ret[1] = new int[1][1];
for (int i = 2; i <= max; i++) {
ret[i] = new int[factorial(i)][];
int[] remaining = new int[i];
for (int j = 0; j < i; j++) {
remaining[j] = j;
}
permutationGen(i, ret[i], 0, new int[0], remaining);
}
return ret;
}
/**
* calculate the factorial of a number.
* The factorial is the number of permutations available for a given set of values.
* @param n the number to calculate
* @return the factorial (n!)
*/
private static int factorial(int n) {
int ret = n;
while (--n > 1) {
ret *= n;
}
return ret;
}
/**
* Recursive function to calculate the permutations of a dataset of a specified size.
* @param size The number of elements to calculate the permutations for
* @param store The place to store the permutations
* @param nextstore the next location to save values in the store
* @param used the positions that have been used in already in building the current permutations
* @param remaining the remaining positions that need to be used.
* @return the index of the next permutation to save
*/
private static int permutationGen(final int size, final int[][] store, int nextstore, final int[] used, final int[] remaining) {
if (used.length == size) {
store[nextstore] = used;
return nextstore + 1;
}
int [] nremain = Arrays.copyOfRange(remaining, 1, remaining.length);
for (int r = 0; r < remaining.length; r++) {
int [] nused = Arrays.copyOf(used, used.length + 1);
if (r > 0) {
nremain[r - 1] = remaining[r - 1];
}
nused[used.length] = remaining[r];
nextstore = permutationGen(size, store, nextstore, nused, nremain);
}
return nextstore;
}
/**
* Recursive combination function. It determines all possible combinations for a set of data, and for
* each combination it also then runs through all permutations.
* With the permutations it checks to see whether the word created by that combination/permutation is
* a real word, and if it is, it adds it to the anagrams solution set.
* @param words the valid words
* @param chars the actual characters we can use to anagram
* @param charpos the position in the chars that we are currently processing
* @param current the letters we currently have in our combination already.
* @param currentlen the number of letters in current that are valid.
* @param permutes the possible permutations for different-sized datasets.
* @param anagrams where to store the valid words when we find them.
*/
private static void checkCombinations(final String[] words, final char[] chars, final int charpos,
final char[] current, final int currentlen, final int[][][] permutes, final Collection<String> anagrams) {
if (currentlen >= current.length) {
return;
}
for (int i = charpos; i < chars.length; i++) {
current[currentlen] = chars[i];
// This is th recursive function to calculate combinations.
checkCombinations(words, chars, i + 1, current, currentlen + 1, permutes, anagrams);
// for each combination, run through all the permutations.
char[] strchr = new char[currentlen + 1];
for (int[] perm : permutes[currentlen + 1]) {
for (int j = 0; j <= currentlen; j++) {
strchr[j] = current[perm[j]];
}
String word = new String(strchr);
if (Arrays.binarySearch(words, word) >= 0) {
anagrams.add(word);
}
}
}
}
public static void main(String[] args) throws IOException {
System.out.println("Reading Linux words file (typically /usr/share/dict/linux.words)");
String words[] = Files.readAllLines(Paths.get("linux.words"), StandardCharsets.UTF_8).toArray(new String[0]);
System.out.println("Convert all to lowercase");
for (int i = 0; i < words.length; i++) {
words[i] = words[i].toLowerCase();
}
System.out.println("Sort all words (" + words.length + ")");
Arrays.sort(words);
char[] chars = "abcdef".toLowerCase().toCharArray();
Set<String> anagrams = new TreeSet<>();
System.out.println("building permutations for " + chars.length + " sizes");
int[][][] permutations = permutations(chars.length);
System.out.println("calculating combinations and permutations of '" + new String(chars) + "'.");
long time = System.nanoTime();
checkCombinations(words, chars, 0, new char[chars.length], 0, permutations, anagrams);
System.out.printf("Found %d words.... in %.3fms\n", anagrams.size(), (System.nanoTime() - time) / 1000000.0);
for (String s : anagrams) {
System.out.println(s);
}
}
}