返回Set<Set<Integer>>的组合生成方法输出不一致问题求助

需求背景 #

为加深对Set类的理解，需要实现组合生成功能：组合是从指定大小集合中选取指定数量元素的方式，从n个元素的集合中选k个元素的组合数为n! / (k! * (n-k)!)。输出为k个元素索引（从零开始）组成的Set的集合，示例：n=3，k=2时，输出[[0,1], [1,2], [0,2]]。

实现代码 #

public static Set<Set<Integer>> generateCombinations(int n, int k) {
    Set<Set<Integer>> totalCombinations = new HashSet<>();

    int total = (n == 0 || k == 0 || n < k)
            ? 0
            : (n == k)
                    ? 1
                    : factorial(n) / (factorial(k) * factorial(n - k));

    while (totalCombinations.size() < total) {
        Set<Integer> combination = new HashSet<>();

        while (combination.size() < k) {
            combination.add((int) (Math.random() * n));
        }
        totalCombinations.add(combination);
    }
    return totalCombinations;
}

public static int factorial(int n) {
    return n * ((n > 1) ? factorial(n - 1) : n);
}

注：计算组合数的三元表达式用于替代处理除零异常的try-catch块。

测试结果 #

正常工作的输入输出 #

generateCombinations(3, 2): [[0, 1], [0, 2], [1, 2]]
generateCombinations(3, 1): [[0], [1], [2]]
generateCombinations(1, 2): []
generateCombinations(0, 6): []

异常的输入输出 #

generateCombinations(14, 4): [[2, 9, 10, 12], [3, 5, 12, 13], [4, 10, 11, 12], [6, 8, 12, 13], [1, 2, 4, 8], [0, 5, 6, 7], [0, 3, 7, 10], [1, 2, 7, 12], [2, 5, 8, 9], [1, 2, 9, 13], [1, 4, 8, 13], [1, 7, 8, 13], [0, 7, 10, 12], [3, 4, 11, 12]]
generateCombinations(15, 4): [[4, 9, 10, 13], [0, 1, 4, 5]]
generateCombinations(15, 2): []
generateCombinations(13, 2): [[0, 1], [0, 2], [0, 3], [0, 7], [3, 4], [3, 5], [1, 7], [2, 7], [3, 6], [1, 8], [1, 10], [0, 12], [1, 11], [1, 12], [2, 12], [4, 10], [6, 9], [7, 8], [3, 12], [4, 12], [7, 10], [8, 10], [7, 11], [9, 10]]

排查思路 #

1. 核心问题：阶乘计算的整数溢出 #

Java的int类型最大值为2147483647，而13!的结果为6227020800，已经超出int的取值范围，会触发整数溢出，导致阶乘结果变成负数或错误的小数值。

• 比如计算C(15,2)时，正确组合数是105，但由于factorial(15)溢出，最终计算出的total值错误（可能为0或负数），导致循环条件totalCombinations.size() < total不成立，直接返回空集合。
• 对于n>=13的场景，factorial(n)都会溢出，进而导致组合数计算完全错误，循环无法生成足够的组合。

2. 辅助验证方法 #

添加日志打印factorial(n)、factorial(k)、factorial(n-k)以及最终total的值，观察是否出现异常数值（比如负数、远小于实际组合数的正数）。

3. 修复方向 #

• 解决溢出问题：将factorial方法的返回类型改为long，扩大数值存储范围；或者改用迭代方式计算组合数，避免直接计算大数阶乘（比如C(n,k)=C(n,k-1)*(n-k+1)/k）。
• 优化组合生成逻辑：随机生成+去重的方式效率极低，尤其是n和k较大时，重复概率高，建议改用回溯、迭代等确定性算法生成所有组合，既保证正确性又提升效率。

内容的提问来源于stack exchange，提问作者Kemper Lee