解決不重復(fù)序列的全排列問題的兩個(gè)方法：遞歸和字典序法

簡介

給定 {1, 2, 3, , , n}，其全排列為 n! 個(gè)，這是最基礎(chǔ)的高中組合數(shù)學(xué)知識。我們以 n=4 為例，其全部排列如下圖（以字典序樹形式來呈現(xiàn)）：

我們很容易想到用遞歸來求出它的所有全排列。

仔細(xì)觀察上圖，

以 1 開頭，下面跟著 {2, 3, 4} 的全排列；

以 2 開頭，下面跟著 {1, 3, 4} 的全排列；

以 3 開頭，下面跟著 {1, 2, 4} 的全排列；

以 4 開頭，下面跟著 {1, 2, 3} 的全排列。

代碼如下：

/**

*

* author : 劉毅（Limer）

* date : 2017-05-31

* mode : C++

*/

#include

#include

usingnamespacestd;

voidFullPermutation(intarray[],intleft,intright)

{

if(left==right)

{

for(inti=0;i

cout<

cout<

}

else

{

for(inti=left;i<=?right;i++)

{

swap(array[i],array[left]);

FullPermutation(array,left+1,right);

swap(array[i],array[left]);

}

}

}

intmain()

{

intarray[4]={1,2,3,4};

FullPermutation(array,0,3);

return0;

}

運(yùn)行如下：

咦~ 遞歸寫出的全排列有點(diǎn)不完美，它并不嚴(yán)格遵循字典序。但是熟悉 C++ 的朋友肯定知道另一種更簡單，更完美的全排列方法。

定義于文件 內(nèi)的兩個(gè)算法函數(shù)：

1、next_permutation，對于當(dāng)前的排列，如果在字典序中還存在下一個(gè)排列，返回真，并且把當(dāng)前排列調(diào)整為下一個(gè)排列；如果不存在，就把當(dāng)前排列調(diào)整為字典序中的第一個(gè)排列（即遞增排列），返回假。

2、prev_permutation，對于當(dāng)前的排列，如果在字典序中還存在上一個(gè)排列，返回真，并且把當(dāng)前排列調(diào)整為上一個(gè)排列；如果不存在，就把當(dāng)前排列調(diào)整為字典序中的最后一個(gè)排列（即遞減排列），返回假。

/**

*

* author : 劉毅（Limer）

* date : 2017-05-31

* mode : C++

*/

#include

#include

usingnamespacestd;

voidFullPermutation(intarray[])

{

do

{

for(inti=0;i

cout<

cout<

}while(next_permutation(array,array+4));

}

intmain()

{

intarray[4]={1,2,3,4};

FullPermutation(array);

return0;

}

運(yùn)行截圖省略。輸出結(jié)果正好符合字典序。

那這個(gè) “輪子” 是怎么做的呢？（摘自侯捷的《STL 源碼剖析》）

1、next_permutation，首先，從最尾端開始往前尋找兩個(gè)相鄰元素，令第一元素為*i，第二元素為*ii，且滿足*i < *ii，找到這樣一組相鄰元素后，再從最尾端開始往前檢驗(yàn)，找出第一個(gè)大于*i的元素，令為*j，將 i，j 元素對調(diào)，再將 ii 之后的所有元素顛倒排列，此即所求之 “下一個(gè)” 排列組合。

2、prev_permutation，首先，從最尾端開始往前尋找兩個(gè)相鄰元素，令第一元素為*i，第二元素為*ii，且滿足*i > *ii，找到這樣一組相鄰元素后，再從最尾端開始往前檢驗(yàn)，找出第一個(gè)小于*i的元素，令為*j，將 i，j 元素對調(diào)，再將 ii 之后的所有元素顛倒排列，此即所求之 “上一個(gè)” 排列組合。

代碼如下：

boolnext_permutation(int*first,int*last)

{

if(first==last)returnfalse;// 空區(qū)間

int*i=first;

++i;

if(i==last)returnfalse;// 只有一個(gè)元素

i=last;

--i;

for(;;)

{

int*ii=i;

--i;

if(*i< *ii)

{

int*j=last;

while(!(*i< *--j))??// 由尾端往前找，直到遇上比 *i 大的元素

;

swap(*i,*j);

reverse(ii,last);

returntrue;

}

}

if(i==first)// 當(dāng)前排列為字典序的最后一個(gè)排列

{

reverse(first,last);// 全部逆向排列，即為升序

returnfalse;

}

}

boolprev_premutation(int*first,int*last)

{

if(first==last)returnfalse;// 空區(qū)間

int*i=first;

++i;

if(i==last)returnfalse;// 只有一個(gè)元素

i=last;

--i;

for(;;)

{

int*ii=i;

--i;

if(*i> *ii)

{

int*j=last;

while(!(*i> *--j))// 由尾端往前找，直到遇上比 *i 大的元素

;

swap(*i,*j);

reverse(ii,last);

returntrue;

}

}

if(i==first)// 當(dāng)前排列為字典序的第一個(gè)排列

{

reverse(first,last);// 全部逆向排列，即為降序

returnfalse;

}

}

結(jié)后語

這篇文章主要介紹了解決不重復(fù)序列的全排列問題的兩個(gè)方法：遞歸和字典序法。