Find the total unique permutations of a char[]?

Question

So I'm working on a little project and I want to write a method that computes the total possible unique permutations of a char[]. The formula for this would be

n!/ possible duplicates

Meaning if I had the word toffee it would be

6!/(2!*2!)

As there are 6 letters total, and 2 duplicate letters that each show up twice.

My first issue is there doesn't seem to be a standard method for computing factorials. Also, the only way I can think of to figure out the possible duplicates, is to scan the whole array and keep track of how many times each letter shows up. Is there a better/more efficient way to do this? All I simply need as a return is a number of total possible unique permutations.

Answer 1

Converting the array to a Set would remove duplications, but it won't tell you what duplications were removed, so it seems to have no choice but to iterate the array and count the number of occurrences per character:

private static Map<Character, Integer> countChars(char[] arr) {
    Map<Character, Integer> counts = new HashMap<>();
    for (char c : arr) {
        Integer count = counts.get(c);
        if (count == null) {
            count = 1;
        } else {
            count += 1;
        }
        counts.put(c, count);
    }
    return counts;
}

With regard to calculating factorials - the JDK indeed doesn't have such a facility. There are several third party libraries that provide it, such as Apache Commons' CombinatoricsUtils, or you could just implement it yourself:

private static final long factorial (int i) {
    if (i == 0) {
        return 1L;
    }
    return i * factorial(i - 1);
}

And then, just put it all together:

private static long numPermutations(char[] arr) {
    long result = factorial(arr.length);
    Map<Character, Integer> counts = countChars(arr);
    for (Integer i : counts.values()) {
        // Note that 1! = 1
        result /= factorial(i);
    }
    return result;
}

EDIT:
Java 8's streaming APIs provide you a more elegant (or at least shorter. Elegance is really a matter of opinion) method of implementing coutChars:

Map<Character, Long> counts = 
    new String(arr).chars()
                   .boxed()
                   .collect(Collectors.groupingBy(o -> (char) o.intValue(), 
                            Collectors.counting()));