1.4.3　排列问题

1．问题描述

有n个元素，它们的编号为1，2，…，n，排列问题的目的是生成这n个元素的全排列。采用一个具有n个存储单元的数组A来存放所生成的排列，假定初始时n个元素已按编号次序由小到大存放在数组A中，即数组中存放的是元素的编号。

2．算法设计思路

为解决该问题，首先要进行认真思考，以便找出生成元素全排列算法的内在规律性，也即分析出递归关系，还需找到算法的停止条件，进而推导出递归关系式，最终设计出递归函数，即构建递归体。

具体设计过程如下：

（1）将规模为n的排列问题转化为规模为n-1的排列问题。

步骤1：数组的首元素定为1，即排列的第一个元素为1，还需要生成后面n-1个元素的全排列。

步骤2：将数组的第一个元素和第二个元素互换，使得数组的首元素为2，即排列的第一个元素为2，还需要生成后面n-1个元素的全排列。

……

步骤n：将数组的第一个元素和第n个元素互换，使得数组的首元素为n，即排列的第一个元素为n，还需要生成后面n-1个元素的全排列。

（2）将规模为n-1的排列问题转化为规模为n-2的排列问题。

对于上述n个步骤，每一步均要按以下步骤进行操作，以步骤1为例进行讲述。

步骤1-1：数组的第二个元素为2，即排列的第二个元素为2，还需要生成后面n-2个元素的全排列。

步骤1-2：数组的第二个元素和第三个元素互换，使得数组的第二个元素为3，即排列的第二个元素为3，还需要生成后面n-2个元素的全排列。

……

步骤1-（n-1）：数组的第二个元素和第n个元素互换，使得数组的第二个元素为n，即排列的第二个元素为n，还需要生成后面n-2个元素的全排列。

同理，将问题的规模一级一级降至1，1个元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其他的排列。

3．算法描述

从上述算法的设计过程可以看出，使用递归技术来解决全排列问题是很容易的。

假定排列算法perm（A，k，n）的功能是：生成数组A后面k个元素的排列。当k=1时，只有一个元素，已构成一个排列。当1<k≤n，可由算法perm（A，k-1，n）生成数组A后面k-1个元素的排列，为完成数组A后面k个元素的排列，需要逐一将数组第n-k个元素与数组中第n-k～n-1个元素互换，每互换一次，就执行一次perm（A，k-1，n）。该问题的算法描述如下：

     void perm(int A[],int k,int n )         //参数k是当前递归层需完成排列的元素个数
        {
           int i;
           if(k==1)                          //已构成一个排列,将其输出
                for(i=0;i<n;i++){
                     cout<<A[i]<<;
                cout<<endl;}
            else
                for(i=n-k;i<n;i++)
                  {
                     swap(A[i],A[n-k]);      //swap为完成元素互换的函数
                     perm(A,k-1,n);
                     swap(A[i],A[n-k]);
                  }
        }