排列组合生成问题的讨论（一）

问题描述

    假设我们给定一组字符或者数字，如何求出它们的全排列或者给定个数的排列组合呢？这个问题本身看起来很简单。从以前学过的数学知识来看的话也很好表述。只是因为这个问题里牵涉到的各种条件和变化比较多，逐个讨论下来的篇幅也很大，所以打算拆成几篇文章来讨论。在这篇文章里，我们主要讨论基本的全排列和它的生成算法。

 

分析

    这个问题我们可以采用两种不同的方式来分析和处理，一种是递归调用的思路，还有一种是字典序的思路。在一些问题的变体里，还会对于排列的输出顺序有一定要求。我们在这里结合具体情况一并讨论。

 

递归

    递归的思路其实还是比较好理解的，比如说我们有一组共n个元素。我们要生成它们的排列时，可以按照一个这样的顺序。首先从数组的第一个元素开始，比如说它可以放置的元素有n个，有n种可选项。而在第一个位置确定之后，后面的元素接着再放，它只有n - 1种可能了。实际上，我们后面每一个位置的元素都和前面的元素有一定关系，比如位置为k的元素必须取和前面元素不一样的。所以我们每次在一个位置上添加元素的时候还要判断一下，是否前面已经有这个元素了。如果有的话则不能添加。所以说，我们可以采用这样的思路，针对每个位置去遍历我们n个元素，尝试将元素赋值到该位置，然后根据前面元素是否被取用来过滤一些被占用的情况。

    所以，根据前面的讨论，我们需要的参数应该包括有如下几个：

1. 已经确定的填充序列，比如说当我们填充到位置i的时候，前面i - 1个元素是已经确定了的。

2. 剩下的需要进行全排列的元素集合s，我们要从这里挑选。

    根据这些讨论，我们这个算法的实现伪码如下：

void permutation(int[] a, 集合s，当前位置cur) {
    if(s为空)  输出序列a.
    else 按照顺序考虑s的每个元素{
        if(s中的元素i 不在a中)
            permutation(a, s - i, cur +1);
    }
}

    我们再来结合具体的实现来考虑一下。假设我们考虑的就是一串数字从1到n。那么这里的参数集合s可以直接用一个数字n来表示。我们可以根据cur == n来判断集合是否为空。因为按照前面递归的关系，每次cur递归一次就要加一，等它遍历完整个集合，也就是集合剩下的元素为0了。所以我们对应的实现如下：

public static void permu(int[] a, int len, int cur) {
        if(a == null || len < 1)
            return;
        if(cur == len) { //判断集合s是否为空
           printList(a); 
        } else {
            for(int i = 1; i <= len; i++) {
               if(!contains(a, i, cur)) {
                    a[cur] = i;
                    permu(a, len, cur + 1);
                }
            }
        }
    }

    这部分代码基本上是前面伪码的详细翻译。其中参数len表示数组的长度。因为cur表示当前放置元素所在的下标，一般是从0到len - 1。 这里有一个开始有点让人费解的地方就是为什么判断集合s为空的时候是if(cur == len)。照理说说cur最多也只能到len - 1啊。其实因为我们要将里面所有的元素都放置满。而放置的最后一个元素就是当cur == len - 1的情况。所以按照前面的递归关系它是要继续到cur + 1的情况。而这个时候正好应该是我们程序的一个返回点了。所以正好就是判断cur是否等于len。一个小细节，容易出问题的地方。我们调用这个方法的时候一般是传入对应的数组，数组长度和开始位置，这个开始位置设置为0。

    另外，里面的contains方法用来判断在给定的cur范围内，是否存在元素i。它的实现如下：

private static boolean contains(int[] a, int i, int pos) {
        for(int j = 0; j < pos; j++)
            if(a[j] == i)
                return true;
        
        return false;
    }

   而里面的printList()方法纯粹是为了输出列表里的元素省事，它的实现如下：

private static void printList(int[] a) {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

     这部分很简单，不解释。

 

字典序生成排列

    还有一种常用的非递归算法叫做字典序生成法。它实际上遵循的是一种数字和排列的一一对应关系。而且我们知道对于两个串来说，我们要比较它们的字典序是按照这样的规则来的：从前面的字符开始比较，一直比较到不同的两个元素为止。如果不同的元素中，某一个序列的元素大，则这个序列整体大于另外一个序列。 比如说我们有两个字符串序列，分别为"abcde", "abcfd"。在这两个串里，前面三个字符是相同的，但是第四个元素一个是d一个是f。因为f > d，所以第二个串大于第一个串。对于数字的串来说就更加明显了。

    按照我们描述的字典序，对于一个串来说，它的元素排列之间就构成了一个顺序关系。比如以我们的数字串1234为例。这4个数字能构成的排列里，最小的是1234, 最大的是4321。我们要生成它们所有的排列，无非就是从最小的1234开始，然后按照一个逐步递增的方式，使得它们生成一个严格递增的序列一直到最大。这样我们既按照原来的要求生成了给定序列的全排列，同时还保证了生成的排列是严格按照递增的顺序生成的。那么，这个详细的生成思路，该怎么来推导呢？

     我们以给定的数字1234为例来考虑。比它大的且与它最接近的数字是1243。通过这一步的观察，作为最低两位的数字，如果它们是保持递增关系的，我们只要调换一下它们的顺序就可以了。我们再往下一步观察，下一个最接近它且大于它的数字是1324。因为此时1243里2后面的数字已经到了所能取的最大数字了，要再增加的话只能增加2。而这里最接近的就是将2换成3。那么后面可以选择的数字是2和4。而很显然，1324是最接近的，而不是1342。那么通过这一步，我们能找到什么规律呢？

     首先一个，当我们取到1243的时候，怎么会考虑到要换的是2而不是其他位置的数字呢？正如前面所说的那样，因为这个时候2后面的数字已经到最大了，也就是说它已经是一个连续严格递减的序列了。比如这里的是43。那么，我们要找到需要换的位置2， 首先就必须要找到一个最后面的连续递减序列。换一种说法，我们也可以说要找到一个最后面的递增序列。比如当1243的时候，我们要保证有这么一个连续递增的序列。我们能找到的最后的那个就是24。所以说这里就确定了2的位置。这一步的过程如下图所示：

    在知道了这个要换的元素之后，我们后面要做的应该就是找一个后面和它最接近但比它大的元素，然后他们之间换个位置。如下图：

    但是很明显，我们只是这一步还是不够的。因为比1243大且最接近它的是1324而不是1342。所以我们肯定还必须要调整。结合我们前面考虑的结果。当我们取到的数字2的时候，它后面肯定是一个递减的序列，或者极端的情况就是它后面只有一个唯一的比它大的元素。既然2后面的这个数字是后面这个递减序列里最大的数字，而处于要让后面数字最接近前面的那个数字，必然必须要取一个尽量小的数字。所以必须要这个最大的数字尽量放到最后面。怎么来让后面这一截数字组成一个最小的数字呢？我们先来看一个这样的规律。

    在前面的序列里，假定每个元素都是唯一的。比如有a[i], a[i+1], a[i+2]...a[i+k]...a[n]这么一个满足a[i] < a[i+1]且从a[i+1]到后面的所有元素都是递减的。那么假设那个大于a[i]且和a[i]最接近的是a[i+k]，那么我们将a[i]和a[i+k]的位置替换之后，a[i+1]到a[n]这一串里还保持有原来的递减特性吗？仔细一想，这个特性是当然满足的。因为我们在前面的步骤里要找这个大于a[i]且最接近a[i]的元素。这里的a[i+k]满足的话，则a[i+k+1]则必然小于a[i]了。不然我们肯定选择的是a[i+k+1]。所以说，这一特性是满足的。而结合我们前面讨论的，要构成一个最小的数列，则只要构造一个严格从小到大的序列就可以了。而既然前面已经是一个严格递减的序列了，我们把它倒一下不就完了吗？

    以我们前面的示例来看，它在交换了2和3之后，要做的就是将2后面的所有元素都倒置一下，如下图：

    这样，最终的排列结果如下：

    尼玛，搞半天原来是这样啊！求一个排列的下一个字典序的过程可以概括成如下的步骤：

     1. 求里面最后面的连续递增元素点。比如说，在前面的示例1243里，肯定最靠后的就是24, 所以找到元素位置2。

    2. 从位置2的这个点，也就是满足最后连续递增的点后面起去找一个比这个元素大，但是最接近这个元素的点。比如说这里找到的是3 。

    3. 交换两个元素的位置。

    4. 再对最后连续递增点后面所有的元素顺序逆转一下。

    有了这个之后，我们要求所有的排列也就简单了，就是一直不停的找下一个字典序序列，直到找不到这个序列为止。我们知道当元素处于一个严格递减的序列情况时，就找不到递增的位置了。这个时候终止程序。在前面的实例里就是达到了4321这个序列。

    好了，到这个份上，就没什么好说的。代码伺候：

1. 找最后的连续递增序列点：

 

private static int findJ(int[] a) {
        for(int i = a.length - 2; i >= 0; i--) {
            if(a[i] < a[i + 1])
                return i + 1;
        }
        return -1;
    }

    从后往前找，找到就直接返回，省事。

 

2. 根据找到的点后面找最接近的大于它的元素：

private static int findK(int[] a, int n, int i) {
        for(int j = n; j > i; j--) {
            if(a[j] > a[i])
                return j;
        }

        return -1;
    }

    我们看到这部分代码的时候可能会有点疑惑。因为是要找到最接近它的元素，这里直接碰到一个比它大的就返回，这样找到的真的就是那个元素吗？其实从前面的推导里已经看到了，后面的元素要么就是纯递减的，要么就一个光杆元素。所以从后往前去找到，第一个符合条件的就是。

 

3. 倒置后面序列里的元素：

private static void reverse(int[] a, int l, int r) {
        while(l < r) {
            swap(a, l, r);
            l++;
            r--;
        }
    }

    里面swap方法的实现如下：

public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

  前面提到的交换元素的步骤放在所有步骤整合的代码里。整合代码的实现如下：

public static void permu(int[] a, int l) {
        while(true) {
            printList(a);
            int j = findJ(a);
            if(j == -1)
                return;
            int k = findK(a, l, j - 1);
            if(k == -1)
                return;
            swap(a, j - 1, k);
            reverse(a, j, l);
        }
    }

    方法里参数l表示数组的长度减一，表示数组里最后一个元素的索引。这里只是实现的一个选择，我们也可以选择数组的长度，只是里面用到的地方要对应的减一。

 

对比

    现在，我们已经实现了递归和非递归的两个版本。我们来比较一下它们的差别。采用递归方法实现的代码总体比较简单。它的基本思路是尝试不断的往每个位置去设定给定的值，然后过滤不符合条件的元素。所以这里的递归的层次和深度是一个值得考虑的地方。它的实现虽然简单，但是在数字比较多的情况下，容易导致栈溢出。而非递归的过程推导占据了很大一部分的篇幅。因为有了这么一个思路，我们不需要使用额外的空间来保存。相对来说空间的复杂度要低一些。

 

可重复集合的排列

    在一些特殊的情况下，我们需要考虑可重复集合里元素的排列。比如说，我们要考虑一个数列1123。对于这个序列，因为有重复元素的加入，整个过程就显得略微复杂一些。因为我们每次将两个1中间的某个1放到一个位置的时候，另外一个1可能放的位置可能会形成一个重复。比如说我们构成的数列2311中，里面两个1都可能交换位置，但是实际上我们要求生成的排列不能重复。也就是说有重复元素的集合生成不重复的排列。所以对于这种有重复元素的排列要去除这些重复。

    为了解决这个问题，我们需要引入一个额外的数组，它专门保存我们需要去读取的数字集合。比如我们前面的数列1123。对于这个数组，因为我们要保存一系列重复的元素，让里面的元素按照顺序排列好有特殊的意义。意义在哪里结合后面的代码会进一步说明。我们再用另外一个数组来保存我们最终放置的元素。

    现在我们来针对两种解决方法进行讨论。

 

递归

    我们在这里先回顾一下前面解决不重复元素全排列的思路。首先遍历源数据集合，尝试从当前的位置设置一个值，然后检查这个值是否已经被前面的元素给占了，如果没有，则尝试下一个位置。

    那么对于我们这里有重复元素的情况，不能简单的判断前面是否已经占用了这个元素，而应该来判断一下，前面如果占用了相同的元素，我们需要看后面是否可以放同样的元素。所以需要判断我们后面可以放的元素个数和已经占用了元素的个数。我们怎么来计算后面可以使用的元素呢？我们可以这样来看，对于前面已经占用的元素，我们可以通过遍历一遍统计出来。而到底可以放多少个同样的元素我们可以去遍历源数据数组，找到比如说这里1的个数有两个，假设前面已经取了一个1的情况下，我们后面还可以取1个。而如果两个1都取了的情况则不能再放置这个元素了。

    按照前面讨论的思路，我们可以写出一个大致过程的伪码：

void repPermu(源数据集合a, 目的数据集合s, int cur) {
    if(目的数据集合满)
        //输出排列;
        print(集合s);
    else 按照源数据集合a中的元素i {
        if(i在a中间出现的次数 > i在s中出现的次数) {
            p[i] = a[i];
            repPermu(a, s, cur+1);
        }
    }
}

    现在，我们根据这部分伪码进一步细化来实现真正的代码。源数据集合和目的数据集合a, s可以分别表示为两个数组。和前面递归实现类似，我们可以用数组长度作为判断是否返回的条件。所以需要一个参数int len。

    我们判断两个集合里给定元素的个数是否相等的实现就只是一个循环遍历，没什么好说的。所以详细的实现如下：

public static void repPermu(int[] a, int[] p, int len, int cur) {
        if(cur == len) {
            printList(p);
        } else {
            for(int i = 0; i < len; i++) {
                if(i == 0 || a[i] != a[i - 1]) {
                    int c1 = 0, c2 = 0;
                    for(int j = 0; j < cur; j++) if(p[j] == a[i]) c1++;
                    for(int j = 0; j < len; j++) if(a[j] == a[i]) c2++;
                    if(c1 < c2) {
                        p[cur] = a[i];
                        repPermu(a, p, len, cur + 1);
                    }
                }
            }
        }
    }

    这里有一个实现的细节值得非常注意。就是为什么我们在for循环的里面要加一个if(i == 0 || a[i] != a[i-1])这样的条件判断呢？这是因为我们在循环里遍历源数组a的时候，如果读到的是连续相同的元素，则它们必然满足a[i] == a[i-1]这样的条件。而i == 0是为了避开当i为0的时候，我们判断i和它前面元素是否相同的这个极端情况。对于前面连续的元素，实际上我们知道，它们同样的情况只应该出现一次，所以要避免重复就体现在这里。而且，在前面我们提到过，这里用a[i] == a[i-1]判断是否有效基于的就是我这个数组a它本身是已经排序了的，所以如果相同的元素肯定就连在一块了。用这个方法来判断就显得很简单。这个部分的理解稍微有点困难。值得细细揣摩。

    在讨论完可重复元素的全排列之后，我们可能也想过是否有非递归的实现呢？实际上，对于非递归的实现，我们用前面现成的那个实现居然也可以。为什么呢？结合我前面讨论的那个选择下一个字典序的排列思路我们就可以推测出来。大家可以去试试，这里就不再赘述了。

 

总结

    这个话题在草稿箱里已经躺了一年多了。当初碰到这样的问题时，总觉得因为都是固定的套路，去刻意的记住它没多大的意义。不过在一次很重要的面试中被别人给问到，结果被一招给放倒了。当时的心情简直是无比郁闷。其实对于排列，以及全排列来说，它的实现方法有很多。除了我们列举的递归和字典序方法，还有一些其他的方法，比如递增进位数制法，递减进位数制法，邻位交换法等。这些方法虽然都有固定的套路，但是他们用来解决这些问题的思路还是很值得借鉴的。后面会结合具体情况进行进一步的讨论。另外，本文主要是讨论了全排列的生成，而对于一些部分排列的情形没有详细说明。在后续文章里也会进一步阐述。

 

参考材料

算法竞赛入门经典

http://www.cnblogs.com/devymex/archive/2010/08/17/1801122.html

http://blog.csdn.net/zmazon/article/details/8351611