java - 求 char[] 的总唯一排列？

Question

所以我正在开发一个小项目，我想编写一个方法来计算 char[] 的所有可能的唯一排列。其公式为

n!/ possible duplicates

意思是如果我有太妃糖这个词，它会是

6!/(2!*2!)

因为总共有 6 个字母，并且有 2 个重复的字母，每个字母都出现了两次。

我的第一个问题是似乎没有计算阶乘的标准方法。另外，我能想到的找出可能重复的唯一方法是扫描整个数组并跟踪每个字母出现的次数。有没有更好/更有效的方法来做到这一点？我所需要的只是返回一些可能的独特排列总数。

Answer 1

将数组转换为Set会删除重复项，但它不会告诉你删除了哪些重复项，所以它似乎别无选择，只能迭代数组并计算出现的次数每个字符:

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

关于计算阶乘 - JDK 确实没有这样的工具。有几个第三方库提供它，例如 Apache Commons 的 CombinatoricsUtils ，或者您可以自己实现:

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

然后，将它们放在一起:

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

编辑:
Java 8 的流式 API 为您提供了一种更优雅(或者至少更短。优雅实际上是见仁见智的问题)的实现 coutChars 的方法:

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