排列数 A(n, m) 与组合数 C(n, m) 的求法 |
您所在的位置：网站首页 › 数列a53怎么算 › 排列数 A(n, m) 与组合数 C(n, m) 的求法 |
排列数 A(n, m) 与组合数 C(n, m) 的求法
|
一、什么是排列，什么是组合？
排列
从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。 组合从 n 个不同元素中，任取 m(m≤n）个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。 通俗地讲 A (排列)：指把几个不但选出来，还要进行排列 如 A 4 2 A_4^2 A42 是指从 4 个物品中选出 2 个来，而且对它们的顺序是有要求的，顺序不一样，结果则不一样。 A 4 2 = 4 × 3 = 12 A_4^2 =4×3=12 A42=4×3=12 C (组合)：是指从 n 个数中选取几个出来，不排列，只组合。如 C 4 2 C_4^2 C42 是指从 4 个中选 2 个，不管它们的内部的顺序。 C 4 2 = C_4^2 = C42= 4 × 3 2 × 1 = 6 \cfrac{4×3}{2×1} = 6 2×14×3=6. 总结：排列与元素的顺序有关，组合与顺序无关。如 231 与 213 是两个排列；2+3+1 的和与 2+1+3 的和是一个组合。
m 就是需要减 1 的次数。 int A(int n, int m) { int res = 1; for (int i = m; i >= 1; i--) { res *= n; //n × n-1 × n-2 × ... n-m，m就是需要减1的次数 n--; } } (2) 组合数与求排列数一样，求组合数也是对公式的实现，不过组合这里有个小技巧可以对代码进行优化，那就是利用组合的互补率： C n m = C n n − m C_n^m = C_n^{ n - m} Cnm=Cnn−m 来减少循环执行次数。 版本一由上可得 C n m = C_n^m= Cnm= A n m m ! \cfrac{A_n^m}{m!} m!Anm，而 m ! m! m! = A m m =A_m^m =Amm，故代码可表达为： int C(int n, int m) { m = Math.min(m, n-m); int numerator = A(n, m); //分子 int denominator = A(m, m); //分母 return numerator / denominator; } 版本二根据 C n m = C_n^m= Cnm= A n m m ! \cfrac{A_n^m}{m!} m!Anm，但我们注意到， A n m A_n^m Anm 的代码实现中，m 一直遍历到 1，所以在方法 A() 的代码实现中我们简单的加入对 m ! m! m! 的求解即可，不需要为了求组合数还得多写一个求排列数的函数。 int A(int n, int m) { int up = 1; //分子 int down = 1; //分母 m = Math.min(m, n-m); for (int i = m; i >= 1; i--) { up *= n; //累乘得到分子 n--; down *= i; //累乘得到分母 } return up / down; } |
由上可得，排列数和组合数的求法代码如下：【本文地址】
今日新闻 |
推荐新闻 |