Skip to main content
Add reference code
Source Link
rolfl
  • 98.1k
  • 17
  • 220
  • 419

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

    }

}

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

    }

}
Source Link
rolfl
  • 98.1k
  • 17
  • 220
  • 419

This problem begs for recursion....

private static final void checkWord(char[] chars, char[]current, int len, List<String> results) {
    if (len == chars.length) {
        final String result = new String(current);
        if (sortedDictionary.contains(result)) {
             results.add(result);
        }
    } else {
        // get the next combination for what is left in the chars
        for int (i = xx; i < yy; i++) {
            current[len] = .... // next char to try
            checkWord(chars, current, len+1 results);
        }
    }
}