找到 char[] 的所有唯一排列？

Question

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

n!/ possible duplicates

意思是如果我有太妃糖这个词，那就是

6!/(2!*2!)

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

我的第一个问题是似乎没有计算阶乘的标准方法。此外，我能想到的找出可能重复项的唯一方法是扫描整个数组并跟踪每个字母出现的次数。有没有 better/more 有效的方法来做到这一点？我只需要作为 return 的所有可能的唯一排列。

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

找到 char[] 的所有唯一排列？

Find the total unique permutations of a char[]?

java

permutation

char

factorial