2.2　排列组合

大部分读者应该对排列组合比较熟悉，因为它在高中的数学课上出现过。与解析几何相比，排列组合的公式简单，并且理解起来比较容易、直观。

排列组合包含两个概念：排列和组合。举个例子，假设某小组一共有5个人，有以下两个问题。

① 从该小组中选出3个人站成一排，一共有多少种排法？

② 从该小组中选出3个人打扫卫生，一共有多少种选法？

对比问题①和问题②可以发现，问题①需要考虑顺序，问题②不需要考虑顺序。这便是排列与组合的区别。问题①要计算排列种类数，排列用字母P（Permutation）或A（Arrangement）表示；问题②要计算组合种类数，组合用字母C（Combination）表示。在计算时，组合种类可以看作排列种类的子集。

可以用形式化的语言描述排列问题，即n个人中计算m个人的排列。继续思考前面的例子，如果要从5个人中选3个人站成一排，那么应该如何选择并排列？首先，从5个人中选择1个人站在位置1上，有5种选法；然后从剩下的4个人中选择1个人站在位置2上，共有4种选法；最后从剩下的3个人中选出1个人站在位置3上，一共有3种选法；因此共有60（5×4×3）种排列方法。这种计算方法就是阶乘。使用字母A表示排列，具体计算公式如下。

由于组合不用考虑选出来的人的排列顺序，因此，只需用计算出来的排列方法总数除以选出人数的排列方法总数。所有排列方法叫作全排列，n个人的全排列总数等于n的阶乘。对于前面的例子，组合方法总数就是10（60 / 3!）种。使用字母C表示组合，具体计算公式如下。

在AI算法中，排列组合主要用于计算特征组合（交叉）后的特征总数。