Java实现组合数学算法（从零开始掌握排列组合计算）

什么是排列与组合？

在深入代码前，我们先简单理解两个核心概念：

• 排列（Permutation）：从 n 个不同元素中取出 m 个元素，按照一定的顺序排成一列。公式为：P(n, m) = n! / (n - m)!
• 组合（Combination）：从 n 个不同元素中取出 m 个元素，不考虑顺序。公式为：C(n, m) = n! / (m! * (n - m)!)

方法一：使用递归计算阶乘

最直观的方式是先实现一个阶乘函数，再代入公式。

public class Combinatorics {    // 计算阶乘 n!    public static long factorial(int n) {        if (n < 0) {            throw new IllegalArgumentException("阶乘参数不能为负数");        }        if (n == 0 || n == 1) {            return 1;        }        return n * factorial(n - 1);    }    // 计算排列数 P(n, m)    public static long permutation(int n, int m) {        if (m > n || m < 0) {            return 0;        }        return factorial(n) / factorial(n - m);    }    // 计算组合数 C(n, m)    public static long combination(int n, int m) {        if (m > n || m < 0) {            return 0;        }        return factorial(n) / (factorial(m) * factorial(n - m));    }    public static void main(String[] args) {        System.out.println("P(5, 3) = " + permutation(5, 3)); // 输出 60        System.out.println("C(5, 3) = " + combination(5, 3)); // 输出 10    }}

虽然这个方法逻辑清晰，但存在明显问题：当 n 较大时（如 n > 20），long 类型会溢出，且重复计算阶乘效率低。

方法二：动态规划优化组合数计算

我们可以利用组合数的递推关系：C(n, m) = C(n-1, m-1) + C(n-1, m)，用动态规划避免重复计算，同时减少溢出风险。

public class OptimizedCombinatorics {    // 使用动态规划计算组合数 C(n, k)    public static long combinationDP(int n, int k) {        if (k > n - k) {            k = n - k; // 利用对称性 C(n, k) = C(n, n-k)        }        long result = 1;        for (int i = 0; i < k; i++) {            result = result * (n - i) / (i + 1);        }        return result;    }    public static void main(String[] args) {        System.out.println("C(10, 3) = " + combinationDP(10, 3)); // 输出 120        System.out.println("C(20, 10) = " + combinationDP(20, 10)); // 输出 184756    }}

这种方法不仅效率高（时间复杂度 O(k)），而且在每一步都进行除法，有效控制中间结果大小，适用于更大的数值范围。

实际应用场景

掌握这些Java组合数学算法后，你可以：

• 生成所有可能的组合（如彩票号码组合）
• 在算法竞赛中快速计算路径数量
• 实现概率统计中的分布函数
• 优化资源分配问题

总结

通过本教程，你已经学会了如何用Java语言实现基本的排列组合算法，并了解了从朴素递归到高效动态规划的优化思路。记住，对于大规模数据，建议使用 BigInteger 类来避免整数溢出。希望这篇Java算法教程能为你打下坚实的组合数学基础！

关键词：Java组合数学、排列组合算法、Java算法教程、组合数计算