C++輸出全排列遞歸算法詳細解釋

C++輸出全排列遞歸算法詳細解釋

中心思想:
設R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R-{ri}.
Perm(X)表示在全排列Perm(X)的每一個排列前加上前綴ri得到的排列。
（1）當n=1時，Perm(R)=(r),其中r是集合R中唯一的元素；
（2）當n>1時，Perm(R)可由(r1)+Perm(R1),(r2)+Perm(R2),…,(rn)+Perm(Rn)構成。

那麼具體程序要怎麼實現呢?我們來個實際的例子,假設有一數列1,2,3,4
那麼1,2,3,4的全排列
perm({1,2,3,4})=1perm({2,3,4})+2perm({1,3,4})+3perm({1,2,4})+4perm(1,2,3)
那麼我們只要將每個數,與第一個數交換不就可以得到下一個序列了嗎?
比如{1,2,3,4}第一個與第二個數交換,那麼不就得到2 {1,3,4}了,接下來我們用一個實際的例子說明該程序是怎樣運行的

具體算法流程:

數列:{1,2,3} 第一個與第一個交換
可以得到1 {2,3} 將序列{2,3}放進perm函數遞歸,然後

——遞歸{2,3}
數列{2,3}第一個與第一個交換
得到2{3} ,輸出1,2,3 (此時low=high,因為序列{3}只有一位數,因此輸出列表list)
數列{2,3}第一個與第一個交換回來,結果仍然是{2,3}
數列{2,3}第一個與第二個交換
得到3{2},輸出1,3,2
{3,2}又第一個與第二個交換回來,變回{2,3}
—–{2,3}遞歸完畢序列恢復原狀{1,2,3}

數列:{1,2,3} 第一個與第二個交換
可以得到2,{1,3}
——遞歸{1,3}
數列{1,3}第一個與第一個交換
得到1{3} ,輸出2,1,3
數列{1,3}第一個與第一個交換回來,結果仍然是{1,3}
數列{1,3}第一個與第二個交換
得到3{1},輸出2,3,1
{3,1}又第一個與第二個交換回來,變回{1,3}
—–{1,3}遞歸完畢
序列{2,1,3}第一個與第二個交換
序列恢復原狀{1,2,3}

數列:{1,2,3} 第一個與第三個交換
可以得到3,{1,2}
——遞歸{1,2}
數列{1,2}第一個與第一個交換
得到1{2} ,輸出3,1,2
數列{1,2}第一個與第一個交換回來,結果仍然是{1,2}
數列{1,2}第一個與第二個交換
得到2{1},輸出3,2,1
{2,1}又第一個與第二個交換回來,變回{1,2}
—–{1,2}遞歸完畢
序列{3,1,2}第一個與第二個交換
序列恢復原狀{1,2,3}

算法可以簡單地寫作
perm({1,2,3})=1perm({2,3})+2perm({1,3})+3perm({1,2})
perm({2,3})=2perm({3})+3perm({2})
perm({1,3})=1perm({3})+3perm({1})
perm({1,2})=1perm({2})+2perm({1})

c++代碼:

#include 
using namespace std;
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void perm(int list[],int low,int high){
    if(low==high){   //當low==high時,此時list就是其中一個排列,輸出list
        for(int i=0;i<=low;i++)
            cout<

程序結果:

123
132
213
231
321
312