排列组合算法公式java-排列组合算法 Java 公式

排列组合算法公式 Java 实战 在 Java 里写算法，别总想着那些教科书里那种“起初、其次、最终”的废话连篇。咱们直接上干货，把难题拆解开，看看如何在脑子里（要么代码里）把逻辑理顺。 排列和组合，看似一样，实际上坑不一样。排列是“顺序关键”，组合是“顺序不关键”。
比如你排一排队伍，甲乙丙排第
一、甲乙排第二，那是排列；要是是选个宝藏，甲乙丙哪位都有，那就是组合。 看个例子就够味了。假设你要从 1 到 5 这五个数字里选 3 个。 先算组合： 从 5 个里挑 3 个，不管顺序，一共能出多少种搭配？公式是 $C_n^m$，也就是 $n! / (m! times (n-m)!)$。代入数字：$5! / (3! times 2!)$ = 10。
这意味着有 10 种组合。
比如 123、124、125、134……不管你是哪位，只要数字对就行。 再看排列： 顺序来了，123 和 321 就算两种吧？那公式就是 $P_n^m$ = $n! / (n-m)!$。代入数字：$5! / 2!$ = 60。
这时候逻辑就通了，不是纯组合，是顺序变了。 实际上写代码时，大量人好办犯“双重循环”的错。
比如想算 $n$ 个数的排列数，要是硬套 $O(n^2)$ 的工夫，那对于大数 n 简直是灾难。得换个思路，直接利用公式。Java 里用 `long` 类型存组合数，前提是结局不超过 `Long.MAX_VALUE`。
要是结局超了，那说明数据本身有点大，用 `BigInteger` 要么 `double` 浮点数（注意精度难题）也行，但逻辑得搞对。 ```java public static long calculateCombinations(int n, int m) { if (m < 0 || m > n) return 0; long res = 1; for (int i = 1; i <= m; i++) { res = res (n - i + 1) / i; } return res; } ``` 这段代码看着好办，但关键点在于顺序。`res = res (n - i + 1) / i`，为啥这样写不炸内存？出于每次乘法一定是下一个整数的整除操作，结局一辈子是个整数。
要是先乘了除以，中间会形成小数，最终再除，可能会出于浮点数精度难题出错，要么溢出。
这种“乘除交替”的操作，大量数学家都靠它存了上百年，只要参数合法，它就稳。 再看排列逻辑，`res = res i` 这种写法，出于每一步都在翻倍，数值增长极快，别一不小心就 `long` 溢出变成了负数要么乱码。
这时候得寻思 `BigInteger`，要么干脆在循环里用 `if` 判断 `Math.pow`，别看不推荐，但在某些极端场景还能活。 实际上算法的核心不在于死记公式，而在于对数据先前的理解。
比如你要算 $n!$，别傻傻地循环乘 $n$ 次，那是 $O(n)$，够慢。
有没有更快的？递归来算阶乘，递归深度有限制，大数会栈溢出。
这时候就得用 `BigInteger` 的构造函数 `new BigInteger(String.valueOf(n))`，要么用流式生成。 组合数那个，$C_{n}^{m} = C_{n}^{n-m}$，这是个技巧。选 3 个从 5 个里，和选 2 个从 3 个里结局一样。代码里能够写 `long res = calculateCombinations(n, n - m)`，这样能不能更快？不一定，但逻辑上更清楚。 另外，面试时千万别说“我认定这个公式挺完美”。要说“寻思到数据范围较大，我用了动态规划要么递归来优化空间复杂度”。把“我认定”换成“寻思到...我用了..."，这味儿就对了。 最终唠叨个冷知识。排列组合不只是数论，它也是概率论的基石。蒙特卡洛模拟里，有时候直接用 $P$ 和 $C$ 来估算期望值，别看不精确，但能跑通，并且代码量极少。 总而言之，把公式背下来没用，得会写，得会判，得会调试。把那段代码当成一个黑盒，你在外部给它喂数据，看它吐出了啥结局，这才是真正掌握它。