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. 总结
排列和组合公式是在数学上已经验证过的公式,本文中所提供的代码,都是使用此公式,解决具体的问题。
领取专属 10元无门槛券
私享最新 技术干货