排列与组合：数学的概念 ++++++++++++++++++++++++++++++ :math:`排列`\ （permutation）与\ :math:`组合`\ （combination）是两个重要的数学概念，是组合数学和概率论的基础，是离散数学、集合论的重要组成部分，在计算机算法上有非常多的应用。这一节我们先来简单介绍一下排列与组合的数学概念。 排列和排列数的计算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 排列是指若干个互不相同物体按顺序排列。比如3个不同的小球，分别编号为1号球、2号球、3号球，那么 [1,2,3] 就是它们的一种排列，[2, 1, 3] 也是一种。参与排列的物体数量比较少的时候，很容易用罗列的方法列出所有可能的排列。比如1到3号三个小球的排列一共有6种，可以很快罗列完整，分别为： .. code-block:: none [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 有时候我们并不想把所有物体都拿出来进行排列，而是指定从中取出若干个进行排列。例如从1号到4号四个小球中取出3个进行排列，经过仔细的罗列，可以得到24种不同的排列： .. code-block:: none [1,2,3], [1,2,4], [1,3,2], [1,3,4], [1,4,2], [1,4,3] [2,1,3], [2,1,4], [2,3,1], [2,3,4], [2,4,1], [2,4,3] [3,1,2], [3,1,4], [3,2,1], [3,2,4], [3,4,1], [3,4,2] [4,1,2], [4,1,3], [4,2,1], [4,2,3], [4,3,1], [4,3,2] 在数学里，:strong:`排列`\ 是指将相异对象或符号根据确定的顺序重排的操作，重排得到的每一个序列都称作一个排列。或者用集合的语言来形容，将一个集合中的元素重排成序列（我们知道，集合中的元素是各不相同且没有相互顺序的，而序列里的元素是有相互顺序关系的）。 从 :math:`n` 个相异对象中任意取 :math:`m` 个进行排列，其中 :math:`0\le m\le n` 且均为整数，可以得到的不同排列的数量，就叫做 :math:`n` 取 :math:`m` 的\ :strong:`排列数`\ ，记作 :math:`P_n^m` 或 :math:`A_n^m`\ ，有时候为了书写方便也简单地写成 :math:`P(n,m)` 或 :math:`A(n,m)`\ 。现在中国的中学数学教材上一般采用 :math:`A_n^m` 这种写法，而计算机教材和大学数学教材上通常使用 :math:`P_n^m` 这种写法，我们使用后一种。如果 :math:`m=n`\ ，即排列所有 :math:`n` 个相异对象的，称作\ :strong:`全排列`\ ，:math:`P_n^n` 也称作 :math:`n` 的\ :strong:`全排列数`\ 。 从前面两个简单的例子可以看出，随着 :math:`n,m` 这两个参数的增大，排列数会迅速增大，而且变得难以手工罗列。事实上，对于任意固定的 :math:`m\gt0`\ ，排列数 :math:`P_n^m` 随着 :math:`n` 增长的阶是阶乘级的，比指数级还高。关于怎样遍历所有排列的算法将在后面介绍，这一节我们先介绍怎样计算排列数。 乍看起来有点奇怪的是，:math:`n` 和 :math:`m` 都是可以等于零的。实际上这也没什么奇怪的，虽然很多人觉得“取0个对象进行排列”，甚至“从0个对象中取出0个进行排列”这种操作很有点神操作的感觉，但在实际上和在数学上都是有意义的，而且毕竟要考虑到空集的情况。当然了，不管对象的总数 :math:`n` 是多少，从中一个对象都不取并进行排列显然只能有一种结果，那就是得到的结果也只能是一个空排列，而这个世界上只有一种空排列。因此我们可以得到排列数的第一条计算规则： .. math:: P_n^0\equiv1 .. note:: 数学符号 :math:`\equiv` 表示“恒等于“。 接下来我们看 :math:`m=1` 的情况，此时当然有 :math:`n\ge1`\ ，也就是从 :math:`n` 个相异对象中取 :math:`1` 个的排列。很显然共有 :math:`n` 种不同取法，分别对应 :math:`n` 个对象。因此这种情况也很简单，我们马上可以得到第二条计算规则： .. math:: P_n^1=n 如果 :math:`m=2`\ ，我们可以这样考虑，每一种排列都可以分两步完成：第1步，先从所有的 :math:`n` 个对象中任取一个，一共有 :math:`n` 中取法；第2步，从剩下的 :math:`n-1` 个对象中再任取一个放在刚才已经取出的那个对象后面，一共有 :math:`n-1` 种取法。上述两步做完就完成了一次 :math:`n` 取 :math:`2` 的排列，根据乘法原理，这样的由先后两步合起来的操作总共有 :math:`n(n-1)` 种，因此就有了第三条计算规则： .. math:: P_n^2=n(n-1) 依此类推，不难得到对于任意的 :math:`m\gt2`\ ，我们不过是不断重复“任取一个，再从剩下的对象里任取一个”这样的操作，把陆续取出的对象依次排在一起，直到取满 :math:`m` 次为止。简单推算一下就知道，最后一次取的时候可供选择的对象还剩 :math:`n-m+1` 个，所以： .. math:: P_n^m=\underbrace{n\cdot(n-1)\cdot\cdots\cdot(n-m+1)}_\text{m个连续递减整数连乘}\tag{1} 当 :math:`m=n` 时，这个连乘会一直延续到1位置，这也和最后一次只剩一个对象可取的实际情况相符。所以全排列数为： .. math:: P_n^n=n\cdot(n-1)\cdot\cdots\cdot1=n! 再仔细观察 :math:`m\ge1` 的几个计算规则，我们可以发现，其实它们本质上都是一样的，都是从 :math:`n` 开始的连续 :math:`m` 个逐个递减的正整数连乘起来，即都可以统一为公式 :math:`(1)`\ 。再考虑到 :math:`n-m+1` 的下一个整数是 :math:`n-m`\ ，以及 :math:`0!=1`\ ，这个公式又可以改写为： .. math:: P_n^m=\frac{n!}{(n-m)!}\tag{2} 而且我们可以发现，公式 :math:`(2)` 也可以包容 :math:`m=0` 的情形。这个公式是数学上计算排列数的标准公式。 .. admonition:: 练习：重复排列（Permutations with repetition） 另外还有一种特殊的排列称为\ :strong:`重复排列`\ 。普通的排列，每一个对象最多只能取一次，而重复排列则允许一个对象被多次取出。有点类似于一个对象被取出之后还可以复制一份放回去以便下次再取，所以有些书上也称之为“可放回的排列”。 :math:`n` 取 :math:`m` 的重复排列数记作 :math:`U_n^m`\ 。请推导它的计算公式，并编程实现。 所以现在有 :math:`(1)` 和 :math:`(2)` 两个公式用于计算排列数，数学推导、证明等常会用到后者，前者多用于计算。计算机程序计算排列数也使用公式 :math:`(1)`\ ，只需用一个循环进行 :math:`m-1` 次乘法即可完成计算，如果用公式 :math:`(2)` 就要计算两次阶乘再相除，会浪费许多工作量。 .. admonition:: 练习：排列数计算 编写计算排列数的工具函数，并编写主程序用来测试。有以下三点要求： 1. 只用一次循环，不对 :math:`m=0,m=1` 等特殊值进行特判； 2. 排列数随着 :math:`m,n` 的增大会变得非常大，注意使用足够大的非负整数类型； 3. 通过测试，对C++语言最大的非负整数类型能够支持的最大排列参数 :math:`m` 和 :math:`n` 有一个大致的估计。 .. hint:: 程序在计算排列数时，如果 :math:`n` 不变，出现 :math:`P_n^{m+1}\lt P_n^m` 的情况，说明 :math:`P_n^{m+1}` 已经超过了取值范围。 .. tip:: ``unsigned long long`` 这个数据类型名称写起来太长，可以在程序最开始的地方写上语句 ``typedef unsigned long long ull;``\ ，以后就可以用 ``ull`` 来代替 ``unsigned long long`` 作为数据类型使用了。 经测试，随着 :math:`n` 和 :math:`m` 的逐步增长，\ ``unsigned long long`` 在 :math:`P_{21}^{19}` 时第一次出现超限，可见排列数的增长速度有多快。 组合和组合数的计算 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 数学里，\ :strong:`组合`\ 是指一种选取操作，和排列不同，组合操作是从一个集合中任意取出指定数量的对象，每一种取法称为一种组合。组合里的对象并不存在相互之间的顺序关系，它们只是单纯地取出来放在一起。例如，从1号到3号三个小球中任取两个的组合一共有三种：{1,2}, {2,3} 和 {1,3}，现在 {1,2} 和 {2,1} 被视为同一种组合，1号球和2号球的相互顺序是无所谓的。 从 :math:`n` 个相异的对象中取 :math:`m` 个总共可以取得的组合种数称为\ :strong:`组合数`\ ，在中国和俄罗斯写为 :math:`C_n^m`\ ，在欧美国家写为 :math:`n \choose m`\ ，我们按照中国习惯用 :math:`C_n^m` 表示 :math:`n` 选 :math:`m` 的组合数，有时候为了书写方便也写作 :math:`C(n,m)`\ 。同样的，如何生成所有组合留到后面介绍，这里先了解组合数怎么计算。 不难发现，组合和排列是非常相似的两种操作，二者唯一的区别是取排列的时候取出的对象相互之间是有位置顺序关系的，可以理解为它们被排成一列队伍，而取组合的时候取出的对象相互之间没有位置顺序关系，可以视为它们只是被凑成了一堆。那么我们可以做下面这样的两步操作：先完成 :math:`n` 选 :math:`m` 的取组合操作，得到所有 :math:`C_n^m` 种组合，其中每一种组合都包含 :math:`m` 个相异的对象。然后我们对所有这些组合做全排列，这样每一种组合都会产生 :math:`P_m^m` 个排列，总共能产生 :math:`C_n^mP_m^m` 个排列，而这正是 :math:`n` 取 :math:`m` 的排列数 :math:`P_n^m`\ ，所以有 :math:`P_n^m=C_n^mP_m^m=m!\cdot C_n^m`\ 。因此就能得出下面的组合数计算公式： .. math:: C_n^m=\frac{P_n^m}{m!}=\frac{n!}{(n-m)!\cdot m!},(0\le m\le n)\tag{3} 这是数学里组合数的标准计算公式。通过这个公式，对几个特殊的 :math:`m` 可以得出一些比较好记而且便利的快捷公式： .. math:: C_n^0=C_n^n\equiv1; C_n^1=C_n^{n-1}=n; C_n^2=\frac{n(n-1)}{2} 回顾本节前面罗列过的从1号到4号四个小球中取出3个进行排列的例子，当时我们经过自己的罗列，列出了总共24个排列。如果把这些排列按照小球编号分类之后，可以分为四类，分别对应4种组合： .. code-block:: none [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 对应 {1,2,3} [1,2,4], [1,4,2], [2,1,4], [2,4,1], [4,1,2], [4,2,1] 对应 {1,2,4} [1,3,4], [1,4,3], [3,1,4], [3,4,1], [4,1,3], [4,3,1] 对应 {1,3,4} [2,3,4], [2,4,3], [3,2,4], [3,4,2], [4,2,3], [4,3,2] 对应 {2,3,4} 通过计算公式，我们可以得到 :math:`C_4^3=\frac{4!}{1!\times3!}=\frac{4\times3\times2\times1}{1\times3\times2\times1}=4`\ ，和上面的列举结果相符。 为了计算方便，也经常会用排列数的公式 :math:`(1)` 来代入计算，从而得到公式 :math:`(3)` 的另一种简化形式： .. math:: C_n^m==\frac{P_n^m}{m!}=\frac{n\cdot(n-1)\cdot\cdots\cdot(n-m+1)}{m\cdot(m-1)\cdot\cdots\cdot1}\tag{4} 值得注意的是，公式 :math:`(4)` 中的分子和分母连乘的次数是一样的，这很便于记忆和计算。组合数在数学和算法题中的运用比排列数更为广泛，也更为灵活和复杂。为了更好地理解掌握，我们还需要在学习几个组合数的基本性质。 **对称性** 反过来观察从 :math:`n` 个对象中任选 :math:`m` 个构成组合的操作，其实也就是从 :math:`n` 个对象中任选 :math:`n-m` 个不用来构成组合，把选剩下的 :math:`m` 个拿来构成组合。比如从苹果、香蕉和西瓜三样水果中选两个要吃的，不就是从它们中间选一个不要吃的嘛。所以 :math:`n` 选 :math:`m` 的取组合和 :math:`n` 选 :math:`n-m` 的取组合其实是没有差别的，相应的，二者的组合数也是没有差别的，这就是组合数的对称性： .. math:: C_n^m = C_n^{n-m}\tag{5} 从组合数计算公式 :math:`(3)` 也可以轻松地发现这个规律，因为二者的计算公式是一模一样的。下面罗列了 :math:`n\le4` 的所有组合数，可以直观地看到其对称性： .. code-block:: none n | m=0 m=1 m=2 m=3 m=4 ---+------------------------ 0 | 1 1 | 1 1 2 | 1 2 1 3 | 1 3 3 1 4 | 1 4 6 4 1 **递推性** 用递推的思路分解从 :math:`n` 个对象中任选 :math:`m` 个构成组合的操作，可以分成两步。首先在 :math:`n` 个候选对象中任意取出其中一个，剩下另外的 :math:`n-1` 个。第二步要分成两种情况，一种是前一步取出的那个对象要被选入组合，那么接下来只要在另外的 :math:`n-1` 个对象中选 :math:`m-1` 个就可以了，一共有 :math:`C_{n-1}^{m-1}` 种选法；另一种是前一步取出的那个对象不要被选入组合，那么接下来需要在另外的 :math:`n-1` 个对象中选 :math:`m` 个，一共有 :math:`C_{n-1}^m` 种选法。以上两种就覆盖了所有选法，没有别的了，于是又有了下面的组合数递推公式： .. math:: C_n^m=C_{n-1}^{m-1}+C_{n-1}^m\tag{6} 当然了，上面的公式完全可以由公式 :math:`(3)` 经数学演算推导得到，请自己尝试一下。 **分组分堆问题** 分组分堆问题在数学和算法领域都是常见问题，比如这样一个问题：有6颗不同口味的巧克力要分给甲乙丙三位小朋友吃，每人2颗，共有多少种分法？我们可以先从6颗巧克力中任选2颗给甲，再从剩下的4颗中任选2颗给乙，剩下的2颗给丙，这样就完成了，一共有 :math:`C_6^2C_4^2C_2^2=15\times6\times1=90` 种分法。 这叫分组问题，即把 :math:`n` 个相异的对象分成 :math:`k` 组，各组分别有 :math:`n_1,n_2,\dots,n_k` 个对象，满足 :math:`n_1+n_2+\cdots+n_k=n`\ ，共有多少种分法？按照依次取组合的方法很容易得到共有 :math:`C_n^{n_1}C_n^{n_2}\cdots C_n^{n_k}` 种，这个数通常记作： .. math:: \begin{align} C_n^{n_1,n_2,\dots,n_k}&=C_n^{n_1}C_{n-n_1}^{n_2}\cdots C_{n_k}^{n_k}\\ &=\frac{n!}{(n-n_1)!\cdot n_1!}\cdot\frac{(n-n_1)!}{(n-n_1-n_2)!\cdot n_2!}\cdot\cdots\cdot\frac{(n_k)!}{(n_k)!}\\ \implies C_n^{n_1,n_2,\dots,n_k}&=\frac{n!}{n_1!\cdot n_2!\cdot\cdots\cdot n_k!} \end{align} 进一步考虑，如果每一个分组中对象的数量相等，而且分好的各个组之间没有顺序差别呢？ 用A、B、C、D、E、F表示6种巧克力，分给甲乙丙。假如有一个分组是 [{A,B}, {C,D}, {E,F}]，表示甲拿到的巧克力是A和B，乙拿到的巧克力是C和D，丙拿到的巧克力是E和F。另有一个分组是 [{C,D}, {A,B}, {E,F}]，那么甲拿到的巧克力是C和D，乙拿到的巧克力是A和B，丙拿到的巧克力是E和F。这两种分组是不同的。 如果题目改成巧克力分完后不是给小朋友吃的，而是装进三个相同的盒子里，还一样吗？不一样了。现在 [{A,B}, {C,D}, {E,F}] 和分组 [{C,D}, {A,B}, {E,F}] 就应该视为是相同的分法了。或许现在我们应该把表示排列的方括号改成表示组合的花括号了，因为很明显这里的区别非常类似从排列到组合的区别。按照前面说过的规律，现在的巧克力分法应该为 :math:`\frac{90}{3!}=15` 种。 这叫做分堆问题，即把 :math:`n` 个相异对象平均分为 :math:`k` 堆，各堆分别有 :math:`n_1,n_2,\dots,n_k` 个对象，堆和堆之间没有位置顺序关系，一共有多少种分法？我们可以先进行分组，而每一个堆一定对应着 :math:`P_k^k=k!` 个组，所以分堆数为： .. math:: \frac{C_n^{n_1,n_2,\dots,n_k}}{k!}=\frac{C_n^{n_1}C_{n-n_1}^{n_2}\cdots C_{n_k}^{n_k}}{k!}=\frac{n!}{n_1!\cdot n_2!\cdot\cdots\cdot n_k!\cdot k!} 实际的分堆问题非常普遍，比如最常见的24支足球队分组比赛，一共可以有多少种分法？图书馆有N本不同的书要放进K个相同的箱子里去有多少种不同的分法？等等。 **二项式定理** 代数学中有一条大名鼎鼎、应用极广的牛顿二项式定理，用以计算二项式的 :math:`n` 次幂 :math:`(a+b)^n` 的展开式，:math:`a,b` 为任意的数或项，:math:`n` 为非负整数。关于二项式的幂，初中阶段就学过几种简单情况： .. math:: (a+b)^0=1,(a+b)^1=a+b,(a+b)^2=a^2+2ab+b^2 如果自己愿意进一步演算，也不难得到 :math:`(a+b)^3=a^3+3a^2b+3ab^2+b^3`\ ，再暴力演算下去怕就有点累了。那么对于任意的 :math:`n` 次幂，伟大的牛顿是怎么考虑的呢？ 按照幂的基本规则，除了0次幂以外，任何东西的 :math:`n` 次幂就是把这东西连续自乘 :math:`n` 次，所以 :math:`(a+b)^n` 就是有 :math:`n` 个 :math:`(a+b)` 连续的自乘起来： .. math:: (a+b)^n = \underbrace{(a+b)\cdot(a+b)\cdot\cdots\cdot(a+b)}_{n个} 所以呢，完全展开之后，合并同类项之前，每一个加项都是在 :math:`n` 中任选若干个 :math:`a`\ ，剩余的选 :math:`b` 然后乘起来得到的。比如说某一项在所有 :math:`n` 个 :math:`(a+b)` 中都选择了 :math:`a`\ ，那么它就成为了那个 :math:`a^n` 项。 一般的情况，如果某一项在 :math:`n` 个 :math:`(a+b)` 中选了 :math:`k` 个 :math:`a`\ ，其中 :math:`0\le k\le n`\ ，剩余的选了 :math:`b`\ ，所以它就是 :math:`a^kb^{n-k}`\ 。那么项 :math:`a^kb^{n-k}` 一共有几个呢？也就是问这样的选择一共可以有几种呢？鉴于乘法是满足交换律的，这样的选择相当于是做 :math:`n` 选 :math:`k` 的组合，一共有 :math:`C_n^k` 种。所以在合并同类项之后项 :math:`a^kb^{n-k}` 的系数一定是 :math:`C_n^k`\ 。 综上所述，代数学里最伟大的定理之一，二项式定理便呼之欲出了： .. math:: (a+b)^n=C_n^0a^0b^n+C_n^1a^1b^{n-1}+\cdots+C_n^ka^kb^{n-k}+\cdots+C_n^na^nb^0\tag{7} .. attention:: 请看，优秀的数学定理总是能优雅地兼容特殊情况，比如 :math:`(a+b)^0=1`\ 。同理，优秀的计算机程序总是能优雅地兼容特殊情况，比如计算排列数的程序对于 :math:`P_n^0=1` 的处理。特判这种东西，虽然有时候很必要，但终归是丑陋的，要设法减少特判的使用。 另外，利用二项式定理还可以得到一个特别有用的推论： .. math:: C_n^0+C_n^1+\cdots+C_n^n=2^n\tag{8} 推导过程极其简单，令 :math:`a=b=1` 就可以了，你想到了吗？ **编程计算组合数** 最后来讲一讲怎么编写程序来计算组合数。首先我们要选择一种最合适的计算公式。 1. 利用公式 :math:`(3)` 固然可以，但是存在大量的计算浪费，不是好的方法，应该选用公式 :math:`(4)` 来减少乘除法次数。 2. 利用公式 :math:`(4)`\ ，分子和分母的乘法次数相同，此时开可以利用对称性公式 :math:`(5)`\ ，对于 :math:`m\lt{n\over2}` 的情况，改为计算 :math:`C_n^{n-m}`\ ，这样有可以减少不少乘除法次数。 3. 利用公式 :math:`(6)` 通过递归调用来实现递推计算看上去也不错，规避了重量级的乘除法，只需要用到速度最快的整数加法运算就可以了。 那么到底用公式 :math:`(4)` 来直接计算还是用公式 :math:`(6)` 来递归计算呢？我们要分析一下它们的时间复杂度。 用公式 :math:`(4)` 计算，肯定要用整数乘除法作为基本运算，分子分母均为 :math:`m-1` 次乘法，时间复杂度为 :math:`O(m)`\ 。 用公式 :math:`(6)` 递归，终止条件为 :math:`m=0` 或 :math:`n=1`\ ，达到终止条件时可以直接返回结果，数据规模和 :math:`m,n` 都相关。设计算 :math:`C_n^m` 的总工作量为 :math:`T(n,m)`\ ，可以得到递推公式 :math:`T(n,m)=T(n-1,m-1)+T(n-1,m)+1`\ ，:math:`T(1,m)=T(n,0)=0`\ ，这个递推公式是一个二元函数，它的计算比较复杂，我们不做要求。有兴趣可以用迭代的方法去试一试，会发现它和二项式定理发生了不可思议的联系，而最终的结果，由于公式 :math:`(8)` 在中间起了一些难以描述的作用，时间复杂度居然是指数级。 所以一般来说计算组合数还是用公式 :math:`(4)` 直接计算好一些。 .. warning:: 虽然组合数比排列数要小规模得多，但也是一类很大的数，\ ``unsigned long long`` 的取值范围只能容纳小规模的组合数。 用公式 :math:`(4)` 计算时要尽可能地用足 ``unsigned long long`` 的取值范围，这并不是想象的那么简单，需要注意以下两个问题： 1. 先计算好分母行不行？对于小的组合数是没有问题，但是不够好，因为计算分母的时候有可能提前造成整型数溢出，使得明明在 ``unsigned long long`` 取值范围内的组合数由于分母计算时提前溢出了而导致结果错误； 2. 如果把计算过程改成一乘一除一乘一除地循环行不行？这是解决提前溢出问题的好办法，而且由于公式 :math:`(4)` 中分子分母的连乘次数相同，所以可以用一个循环完成计算。但是这里有陷阱，计算顺序没有安排对的话，可能造成错误。 如果把计算过程做下面的调整： .. math:: C_n^m=\frac{n\cdot(n-1)\cdot\cdots\cdot(n-m+1)}{m\cdot(m-1)\cdot\cdots\cdot1}=\left({n\over m}\right)\cdot\left({n-1\over m-1}\right)\cdot\cdots\cdot\left({n-m+1\over 1}\right) 那么不能保证每一次乘一个数再除一个数的时候能够整除。比如计算 :math:`C_5^2`\ ，按照上面的方法，第一轮循环计算 :math:`5\over2` 就发生了不能整除的问题，计算结果势必错误。 这时候怎么办？提示一下，2个连续的正整数里一定有一个2的倍数、3个连续正整数里一定有一个3的倍数，......，依此规律，:math:`k` 个连续正整数里一定有一个 :math:`k` 的倍数。所以知道应该怎样调整计算顺序了吧？ .. admonition:: 练习 按照上面所述的要求和讲解，编写一个完美的在 ``unsigned long long`` 范围内的组合数计算工具函数。自行编写主函数来进行正确性测试，并对 ``unsigned long long`` 这种数据类型最多能计算到多大的组合数进行试验。