排列组合的算法设计与C++实现

雷小园

（江西宜春学院 数学与计算机科学学院，江西 宜春 336000）

1 引言

排列和组合是数学和计算机科学中的一项重要内容，很多问题（如旅行商问题、工作分配问题）的求解中都用到了{1,…,n}的全排列。我们知道{1,…,n}的全排列有n！中，那么该如何设计算法来得到所有的排列，并用某种语言编程实现呢？下面详细讨论了四种生成{1,…,n}的全排列的算法，还讨论了一种生成{1,…,n}的字典序r-组合的算法，5种算法都用C++语言编程具体实现（由于篇幅问题，此处没列出C++源程序，需要源程序的本人可以提供）。

2 用换位法生成全排列

设已经得到了{1,…,n-1}的(n-1)！个排列的表，我们可以把n插入到{1,…,n-1}的每一个排列中的n个可能的位置中去，从而得到{1,…,n}的 n(n-1)！=n！个排列的表。

我们开始从左到右把n插入到 12…(n-1)的n个位置中去，然后每处理一个{1,…,n-1}的新排列时，再调转方向。因为这样它满足最小变化要求：仅仅需要交换相邻的两个元素就能得到一个新的排列。

例n=4的情况，如下：

开始1的排列 1

从右到左将2插入1 12 21

从右到左将3插入12，再从左到右将3插入21，得到 123 132 312 321 231 213

对上面得到的6个{1,2,3}的全排列，从右到左将4插入123中，再调转方向从左到右将4插入132，再调转方向依次插入，如下

为了得到{1,…,n}的所有排列，就先得生成并保存{1,…,n-1}的所有排列，而为了生成{1,…,n-1}的所有排列，又必须先生成{1,…,n-2}的所有排列，等等，这样处理和编程都比较困难。

我们可以找到一种方法，不需要保留所有排列的列表，从第一个排列1,…,n开始，每次交换相邻的两个数就得到一个新的排列，得到与上面相同的顺序。为此，我们给每个整数k赋予一个方向，在其上面画一个小箭头来表示：k或k。如果一个整数k的方向指向一个相邻的更小的整数，我们称这个整数是活动的。例如，对 2 6 3 1 4 5，346是活动的。

生成{1,…,n}的排列的算法为：

从12…n开始，重复进行下面3步，直到不存在活动元素。

1)求出一个最大的活动元素k

2)交换k和它指向的相邻元素

3)把所有大于k的元素的方向调转对n=3应用该算法，如下所示：

3 用字典序法生成全排列

上面的算法得到的排列的顺序不是非常自然，我们可以找到一个算法，按字典序生成{1,…,n}的所有的排列。字典序就是像在字典中单词的排列顺序一样，所有的排列按照升序排队。

我们先来看看从一个排列来找下字典序的一个排列。例如，对{1,2,3,4,5,6}的一个排列163542，如何找它的下一个排列。为了按照字典序得到最小的变化，我们应该尽量去换动右面的数字。我们发现最后三个数字是最大的（从右到左一个比一个大），无法再做任何调整。但3小于右面的5，3542不是最大的，故可以换动3。为了使得变化最小，应该在3的后面找一个比3大的最小的数，这可以从右到左找到第一个比3大的数。交换这两个数后形成164532，现在最后三个数依然是从大到小排列的，为使这三个数最小，可以把这三个数逆置，这样便得到163542是下一个排列为164235。

于是，按字典序生成{1,…,n}的所有的排列的算法如下：

将12…n放置到a数组中，重复进行以下步骤

1)从右向左找到第一个减小的元素a[m]，如果不存在这样的元素则结束

2)再从右向左找到第一个大于a[m]的元素a[k]

3)交换a[m]和a[k]

4)将m以后的每个数逆置，得到一个排列

4 用减治-递归法生成全排列

可以采用减治法，把n个数的排列，转化为n-1个数的排列。对{1,…,n}的所有的排列，我们先把1放在首位，把{2,…,n}的n-1个数进行全排列，然后再把2放置在首位，把剩下的n-1个数进行全排列，……，以此类推，就得到{1,…,n}的所有的排列。为了把某个数（比如2）放到首位，可以交换这个数和第一个数，但在对剩下的数进行全排列后，应该再把这两个数交换回来，以保持原有的顺序不变，以便可以继续把第一个数和另一个数（比如3）进行交换。

5 用回溯-递归法生成全排列

回溯法的一个很好的例子是n皇后问题，就是在一个n×n的棋盘上放n个皇后，使得彼此不受攻击。全排列问题可以看作是一个简化的n皇后问题，{1,…,n}的n个元素看做是n个皇后，放到一个1×n的棋盘上，每种放法就对应一个排列。

仿照n皇后问题，得到全排列的回溯算法：先把12…n放置到a数组中，x数组用来记录每个位置所放的是哪个元素，c数组用来记录各个位置是否已经放了数。对于第i个元素i，有n个可能的位置，先看第一个位置，如果可以放就放下去，同时记录该位置已放数据。从第i+1个元素开始将各个元素放到x数组中，当放好第n个数后就得到一个排列。将已放下去的第i个元素拿起来，继续看能否放到下一个位置，放好了第i个元素后继续放置第i+1个元素。

6 组合问题，按字典顺序生成{1,2,…,n}的所有r-组合

前面均为{1,2,…,n}的全排列，下面来研究一下生成{1,2,…,n}的所有r-组合的字典排序算法。

例如，{1,2,…,8}的字典序的5-组合，第一个应该是 12345，最后一个是 45678。对12478，我们来找它的下一个组合。和排列一样，为了得到最小的变化，我们尽量去改动靠右面的数字。最右面两个数字78已是最大无法再增加，而数字4还不是这个位置的最大的数，于是可以把4加1改为5，最后两位也跟着改为尽可能小的数67。于是得到12478的下一个组合是12567。

于是按字典序生成{1,2,…,n}的所有r-组合的算法为

从12…r开始，重复进行进行以下步骤

1)从右到左找到第一个不是该位置的最大值的元素a[m]

2)将该元素加1

3)将该元素以后的元素依次递增，得到一个组合

[1][美]Richard A.Brualdi.组合数学[M].冯舜玺译.北京:机械工业出版社.2002:27-68.

[2][美]Richard Johnsonbaugh.离散数学(第五版)[M].石纯一译.北京:人民邮电出版社.2003:167-182.

[3][美]Anany Levitin.算法设计与分析基础(第2版)[M].潘彦译.北京:清华大学出版社.2007:136-137.