C＋数学与算法系列之排列和组合

1. 前言

本文将聊聊排列和组合，排列组合是组合学最基本的概念，排列组合在程序运用中也至关重要。

排列问题：指从给定个数的元素中取出指定个数的元素进行排序，并统计排序的个数。

组合问题：指从给定个数的元素中仅仅取出指定个数的元素，不排序，并统组合的个数。

2.排列

排列的定义：

从个不同元素中，任取个不同的元素按照一定的顺序排成一列，叫做从个不同元素中取出个元素的一个排列。如从中选择 个数字进行排列，则认为和是两种不同的排列。

从个不同元素中取出个元素的所有排列的个数，叫做从个不同元素中取出个元素的排列数，用符号 表示。

Tips： 排列的英文是 或者 ，故使用   或者 表示都可以，二者含义一样。

计算从 个数字中任选择个数字有多少种排列方式？

解决此问题时，先把问题演变成从 个数字中选择 个数字进行排列，其有多少种方案？

第 数字可以在 个数字中任选择一个，故有 种选择。

因第 个数字已经选择了一个，第 个数字只能在剩下的数字中选择，也就是只能在剩下的 个数字中选择，则有 种选择。

同理，第 个数字有 种选择，第 个数字只有种选择，第五个数字只能有种选择。

所有的排列数是 种方案，是不是看起来很熟悉，就是求 的阶乘。

下面使用穷举法求解上述问题中排列的个数：

既然是求 的阶乘，可以简化程序。

如果不是选择 个数字，而是选择 个数字？

则第 个数字有种选择，第 个数字有种选择，第 个数字有种选择，第 个数字有种选择，最终可选择的个数为，和前面相比较，即为 除以 。

如果不是选择 个数字，而是选择 个数字？

则第 个数字有种选择，第   个数字有种选择，第 个数字有种选择，最终可选择的个数为。即为除以的阶乘。

可推导出从 个数字中选择个数字的排列个数的公式：

从推论可知，求的排列个数可以通过乘法原理求解：

计算排列的个数，先确定高位的可能个数，再逐一确认次高位可能个数，一直到最低位的可能个数……完成它需要分成个步骤。

最高位有 种方法，次高位有种方法……最低位有 种方法。则最终的排列个数有：种。

利用排列公式求解个数的算法：

输出结果：

3. 组合

组合的定义：

从个不同元素中，任取个元素并成一组，叫做从个不同元素中取出个元素的一个组合。

从个不同元素中取出个元素的所有组合的个数，叫做从个不同元素中取出个元素的组合数。用符号 表示。

Tips：   的缩写。

组合与排列的区别：

组合对于找出来的数字的顺序没有要求，也就是说和只能算一种组合方案。

如何统计组合的个数？

可以根据排列公式推导。

如从 选择 个数字进行组合。先套用排列计算公式，共有 种排列方案。即 种方案。求组合个数，则需要减去数字一样、顺序不一样重复方案，最终结果为 。

求解组合的个数可以先求解排列个数后，再排除重复的部分。问题转为具体重复的会有多少？

如果从 个数字中选择 个数字，则任意选择的 个数字会有 种排列方案，但是，对于组合而言，是一种方案。

同时，从个数字中选择 个数字排列，任意个数字会有 种排列。或者说从  个数字中任意选择  个数字，则个数字的排列有种，对于组合而言，这 个排列数只计数 次。

所以，求解个数字中选择个数字的组合数可以先计算排列数后，再在结果上除以 。

在程序中套用上述公式，可以求解出 有 种组合数。

输出结果：

在上述组合公式的基础上，组合公式还可以发生如魔术般的变化，也许这就是数学的神奇之处。

3.1   运算法则一

如下图所示：

通过一个案例求证：假设有 名学生，选择 名学生打扫卫生，有多少种选择？

显然，这是一个组合问题，没有顺序的要求，即。有 种思路求解：

从 个学生中选择 名学生打扫卫生。套用组合的基础公式可知结果=种选择。如下图所示，可以理解为是正向选择。

另一种方案，称为反向选择，因为有 个学生，每次选择一个学生回家，剩下的搞卫生，同样满足要求。相当于 个学生里面选择 名学生。结果 。

组合公式的如上运算法则很容易理解。根据下面的组合公式，可知，从 中选择 和 从 中选择 的最终表达式是一样的。

编程实现：

3.2 运算法则二

如下图所示，当从 中取个数字得到的组合总数，可归纳为求解 中取 个数字的组合数。

直接套用公式验证 和 的结果：

个数字选择 个数字进行组合，结果=。

个数字选择个数字进行组合，结果=。

个数字选择个数字进行组合，结果=。

结论是：。

Tips： 和必须连续！如并不等于。  是成立的。

根据场景验证：

如果有 名学生，需要  名学生留下来搞卫生，显然，可选择方案有 种方案。

换一种理解，如果学号为 的学生必须留下来，显然，只需要在剩下的 名学生中选择 名学生留下来。如果学号为 的学生不留下来，则需要从剩下的 名学生中选择 名。

严格的证明，可以由原始公式直接推导。如下图所示：

编程实现：

3.3  运算法则三

如下图所示：

先直接套用公式验证   的结果。

个数字中选择 个，结果为 。

个数字中选择 个，结果为 。

个数字中选择 个，结果为 。

所以 和 22 结果一样。但这只是个例，不足以证明普适性。

用另一种方式验证公式的合理性：假设现有一个箱子，里面有 个苹果，请问选择任意个苹果数的方案有多少种？

方案一：你的角度。

不选择()，可以认为是 种方案。

选择 个苹果()，可以在 个苹果中任一个，则有 种方案。

选择 2 个苹果()，只有 1 种方案。

。

方案二：苹果的角度。

每个苹果都是独立的个体，可以出来，也可以不出来。所以每个苹果都有 种选择。

箱子中现在有 个苹果，根据乘法原理，也就是 个 相乘（ 的 次方 ）。

所以 22=4。如果有 个苹果，则共有  23 种方案。

编程验证：

3.4 运算法则四

如下图所示：

Tips： 组合公式的上面的数字是相同的，下面的数字必须连续。

可以用选择值日生的例子推导公式的正确。如果需要在学号为 的这 名学生中选择 名学生留下来当值日生，且必须在选择出来的 名学生中指定一人为组长。则选择方案可以由以下的分解方式组成：

学号为 学生当组长，则只需要在剩下的 名学生中选择名学生，即 。

学号为 学生当组长，则只需要在剩下的 名学生中选择名学生，即 。

学号为 学生当组长，则只需要在剩下的 名学生中选择名学生，即 。

学号 当组长，剩下人数不够凑成 个。没得选择。

故 。

3.5 运算法则五

如下图所示：

还是以上面的值日生为例，现在有 名学生， 男 女，需要从 人中选择 3 人留下来值日，其组合数为 ，在所有组合数中一定出现如下的搭配：

没有男生 ，则选择女生，即选择方案有 。

选择 名男 ，则选择女生 ，选择出来的男生可以和选择出来的任一组女生搭配，显然方案数是  。

选择 名男 ，则选择女生 ，共有  种方案。

选择 名男 ，则选择女生 ，共有  种方案。

4. 总结

排列和组合公式是在数学上已经验证过的公式，本文中所提供的代码，都是使用此公式，解决具体的问题。