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.

Possible duplicate of http://stackoverflow.com/q/891031/3788176 — Andy Turner, Sep 19 '15 at 19:45

Mureinik · Accepted Answer · 2015-09-20T03:30:23.323

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

This was very helpful, thank you! I was thinking maybe HashMaps were the best way to go, but wasn't sure about how to do it. Thanks! — Ahley, Sep 19 '15 at 20:08
One thing: on the 4th line of the countChars method you have: Integer count = arr.get(c); I get an error that says cannot invoke get(char) on the array type char[] — Ahley, Sep 19 '15 at 20:17
@AshleyPothier arg, how embarrassing. It's supposed to be `counts.get(c)`. Edited and fixed. My apologies. — Mureinik, Sep 19 '15 at 20:22

Find the total unique permutations of a char[]?

1 Answers1