1.4.3　排列問題

1．問題描述

有n個(gè)元素，它們的編號為1，2，…，n，排列問題的目的是生成這n個(gè)元素的全排列。采用一個(gè)具有n個(gè)存儲(chǔ)單元的數(shù)組A來存放所生成的排列，假定初始時(shí)n個(gè)元素已按編號次序由小到大存放在數(shù)組A中，即數(shù)組中存放的是元素的編號。

2．算法設(shè)計(jì)思路

為解決該問題，首先要進(jìn)行認(rèn)真思考，以便找出生成元素全排列算法的內(nèi)在規(guī)律性，也即分析出遞歸關(guān)系，還需找到算法的停止條件，進(jìn)而推導(dǎo)出遞歸關(guān)系式，最終設(shè)計(jì)出遞歸函數(shù)，即構(gòu)建遞歸體。

具體設(shè)計(jì)過程如下：

（1）將規(guī)模為n的排列問題轉(zhuǎn)化為規(guī)模為n-1的排列問題。

步驟1：數(shù)組的首元素定為1，即排列的第一個(gè)元素為1，還需要生成后面n-1個(gè)元素的全排列。

步驟2：將數(shù)組的第一個(gè)元素和第二個(gè)元素互換，使得數(shù)組的首元素為2，即排列的第一個(gè)元素為2，還需要生成后面n-1個(gè)元素的全排列。

……

步驟n：將數(shù)組的第一個(gè)元素和第n個(gè)元素互換，使得數(shù)組的首元素為n，即排列的第一個(gè)元素為n，還需要生成后面n-1個(gè)元素的全排列。

（2）將規(guī)模為n-1的排列問題轉(zhuǎn)化為規(guī)模為n-2的排列問題。

對于上述n個(gè)步驟，每一步均要按以下步驟進(jìn)行操作，以步驟1為例進(jìn)行講述。

步驟1-1：數(shù)組的第二個(gè)元素為2，即排列的第二個(gè)元素為2，還需要生成后面n-2個(gè)元素的全排列。

步驟1-2：數(shù)組的第二個(gè)元素和第三個(gè)元素互換，使得數(shù)組的第二個(gè)元素為3，即排列的第二個(gè)元素為3，還需要生成后面n-2個(gè)元素的全排列。

……

步驟1-（n-1）：數(shù)組的第二個(gè)元素和第n個(gè)元素互換，使得數(shù)組的第二個(gè)元素為n，即排列的第二個(gè)元素為n，還需要生成后面n-2個(gè)元素的全排列。

同理，將問題的規(guī)模一級一級降至1，1個(gè)元素的排列是它本身，此時(shí)到達(dá)遞推的停止條件。數(shù)組中的元素即為1個(gè)排列，然后進(jìn)行回歸依次得到其他的排列。

3．算法描述

從上述算法的設(shè)計(jì)過程可以看出，使用遞歸技術(shù)來解決全排列問題是很容易的。

假定排列算法perm（A，k，n）的功能是：生成數(shù)組A后面k個(gè)元素的排列。當(dāng)k=1時(shí)，只有一個(gè)元素，已構(gòu)成一個(gè)排列。當(dāng)1<k≤n，可由算法perm（A，k-1，n）生成數(shù)組A后面k-1個(gè)元素的排列，為完成數(shù)組A后面k個(gè)元素的排列，需要逐一將數(shù)組第n-k個(gè)元素與數(shù)組中第n-k～n-1個(gè)元素互換，每互換一次，就執(zhí)行一次perm（A，k-1，n）。該問題的算法描述如下：

     void perm(int A[],int k,int n )         //參數(shù)k是當(dāng)前遞歸層需完成排列的元素個(gè)數(shù)
        {
           int i;
           if(k==1)                          //已構(gòu)成一個(gè)排列,將其輸出
                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為完成元素互換的函數(shù)
                     perm(A,k-1,n);
                     swap(A[i],A[n-k]);
                  }
        }