[科普中國]-全排列

簡介

從n個(gè)不同元素中任取m（m≤n）個(gè)元素，按照一定的順序排列起來，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。當(dāng)m=n時(shí)所有的排列情況叫全排列。

公式：全排列數(shù)f(n)=n!(定義0!=1)，如1,2,3三個(gè)元素的全排列為：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

共3*2*1=6種。

方法以下介紹全排列算法四種：

(A)字典序法

(B)遞增進(jìn)位制數(shù)法

(C)遞減進(jìn)位制數(shù)法

(D)鄰位對換法

字典序法對給定的字符集中的字符規(guī)定了一個(gè)先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個(gè)全排列的先后是從左到右逐個(gè)比較對應(yīng)的字符的先后。

[例]字符集{1,2,3},較小的數(shù)字較先,

這樣按字典序生成的全排列是:123,132,213,231,312,321。

[注意] 一個(gè)全排列可看做一個(gè)字符串，字符串可有前綴、后綴。

1）生成給定全排列的下一個(gè)排列 所謂一個(gè)的下一個(gè)就是這一個(gè)與下一個(gè)之間沒有其他的。這就要求這一個(gè)與下一個(gè)有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。

[例]839647521是1--9的排列。

1—9的排列最前面的是123456789，最后面的是987654321，從右向左掃描若都是增的，就到987654321，也就沒有下一個(gè)了。否則找出第一次出現(xiàn)下降的位置。

[序數(shù)公式]

有從 1 到 n 的連續(xù)的 n 個(gè)自然數(shù)，其全排列按照從小到大排列，次序從 0 到 n!-1 ，總共 n! 個(gè)?，F(xiàn)有其全排列中的一組 “、、……”，其全排列次序?yàn)椋?/p>

遞增進(jìn)位制數(shù)法1)由排列求中介數(shù) 在字典序法中，中介數(shù)的各位是由排列數(shù)的位決定的.中介數(shù)位的下標(biāo)與排列的位的下標(biāo)一致。

在遞增進(jìn)位制數(shù)法中，中介數(shù)的各位是由排列中的數(shù)字決定的。即中介數(shù)中各位的下標(biāo)與排列中的數(shù)字(2—n)一致。可看出n-1位的進(jìn)位鏈。 右端位逢2進(jìn)1，右起第2位逢3進(jìn)1，…，

右起第i位逢i+1進(jìn)1，i=1,2,…,n-1. 這樣的中介數(shù)我們稱為遞增進(jìn)位制數(shù)。 上面是由中介數(shù)求排列。

由序號（十進(jìn)制數(shù)）求中介數(shù)（遞增進(jìn)位制數(shù)）如下：

m=m1,0≤m≤n!-1

m1=2m2+kn-1,0≤kn-1≤1

m2=3m3+kn-2,0≤kn-2≤2

……………

mn-2=(n-1)mn-1+k2,0≤k2≤n-2

mn-1=k1,0≤k1≤n-1

p1p2…pn←→(k1k2…kn-1)↑←→m

在字典序法中由中介數(shù)求排列比較麻煩，我們可以通過另外定義遞增進(jìn)位制數(shù)加以改進(jìn)。

為方便起見，令ai+1=kn-1，i=1,2,…,n-1

(k1k2…kn-1)↑=(anan-1…a2)↑

ai：i的右邊比i小的數(shù)字的個(gè)數(shù)

在這樣的定義下，

有839647521←→(67342221)↑

(67342221)↑+1=(67342300)↑←→849617523

6×8+7)×7+3)×6+4)×5+2)×4+2)×3+2)×2+1 =279905

由(anan-1…a2)↑求p1p2…pn。

從大到小求出n,n-1,…,2,1的位置

_ ... _ n _ _ …_ (an個(gè)空格)

n的右邊有an個(gè)空格。

n-1的右邊有an-1個(gè)空格。

…………

2的右邊有a2個(gè)空格。

最后一個(gè)空格就是1的位置。

遞減進(jìn)位制數(shù)法在遞增進(jìn)位制數(shù)法中，中介數(shù)的最低位是逢2進(jìn)1，進(jìn)位頻繁，這是一個(gè)缺點(diǎn)。

把遞增進(jìn)位制數(shù)翻轉(zhuǎn),就得到遞減進(jìn)位制數(shù)。 (anan-1…a2)↑→(a2a3…an-1an)↓

839647521→ (12224376)↓

(12224376)↓=1×3+2)×4+2)×5+2)×6+4)×7+3)×8+7)×9+6=340989

[注意]求下一個(gè)排列十分容易

鄰位對換法遞減進(jìn)位制數(shù)法的中介數(shù)進(jìn)位不頻繁，求下一個(gè)排列在不進(jìn)位的情況下很容易。

這就啟發(fā)我們，能不能設(shè)計(jì)一種算法，下一個(gè)排列總是上一個(gè)排列某相鄰兩位對換得到的。

遞減進(jìn)位制數(shù)字的換位是單向的，從右向左，而鄰位對換法的換位是雙向的。 這個(gè)算法可描述如下：

對1—n-1的每一個(gè)偶排列，n從右到左插入n個(gè)空檔(包括兩端)，生成1—n的n個(gè)排列。

對1—n-1的每一個(gè)奇排列，n從左到右插入n個(gè)空檔，生成1—n的n個(gè)排列。

對[2,n]的每個(gè)數(shù)字都是如此。

839647521

字典序法 遞增進(jìn)位制法 遞減進(jìn)位制法 鄰位對換法

下一個(gè) 839651247 849617523 893647521 836947521

中介數(shù) 72642321↑ 67342221↑ 12224376↓ 10121372↓

序 號 297191 279905 340989 203393

生成樹生成樹中介數(shù)可以采用樹的結(jié)構(gòu)表示全排列生成算法，以數(shù)字的全排列生成算法為例，從最小的數(shù)1開始，其全排列只有一種可能；加入數(shù)字2，數(shù)字2可以插入在1的后邊或前邊，有兩個(gè)不同位置；

再加入3，對于第二層中的每一種不同排列，都可以通過將3插入不同位置得到三種不同的排列數(shù)，共有6種排列數(shù)；一次類推可以得到 個(gè)數(shù)的全排列。

基于此，可以構(gòu)造一種新的中介數(shù)，其定義如下：

對于生成樹中的第n層，每一個(gè)節(jié)點(diǎn)中介數(shù)的前n-2位繼承于其父節(jié)點(diǎn)的中介數(shù)，中介數(shù)最后一位為該層新加入的數(shù) 減去其右邊相鄰的數(shù)。

如果新加入的數(shù)在最右邊，則中介數(shù)最后一位為0。

如圖所示，排列數(shù)12的中介數(shù)為0，對于生成樹第三層由節(jié)點(diǎn)12擴(kuò)展得到的新節(jié)點(diǎn)，當(dāng)新加入的數(shù)3位于最右邊時(shí)（即排列數(shù)123），對應(yīng)的中介數(shù)為00；若3插入12中間，則中介數(shù)末位為3-2=1，即中介數(shù)為01；類似地排列數(shù)312對應(yīng)的中介數(shù)為02。

不難看出，生成樹中介數(shù)也是遞減進(jìn)位制數(shù)，但和遞減進(jìn)位制數(shù)法是不同的。如排列數(shù)231對應(yīng)的生成樹中介數(shù)為12，而遞減進(jìn)位制數(shù)法對應(yīng)的中介數(shù)為11。

算法完備性不難看出，全排列生成樹每一層的不同節(jié)點(diǎn)對應(yīng)的中介數(shù)都是不同的，這是因?yàn)椋?/p>

（1）每個(gè)子節(jié)點(diǎn)中介數(shù)的前綴都從其父節(jié)點(diǎn)繼承得到，因此不同父節(jié)點(diǎn)生成的子節(jié)點(diǎn)中介數(shù)一定不同；

（2）同一個(gè)父節(jié)點(diǎn)生成的子節(jié)點(diǎn)，父節(jié)點(diǎn)的排列數(shù)每一位都是不同的，因此新加入的數(shù)插入不同位置得到的中介數(shù)的最后一位一定是不同的。

由以上兩點(diǎn)及歸納法即可證明生成樹每一層不同節(jié)點(diǎn)對應(yīng)的中介數(shù)都是唯一不重復(fù)的。又全排列生成樹每一個(gè)節(jié)點(diǎn)的排列數(shù)是無重復(fù)無遺漏的，因此從中介數(shù)到排列數(shù)的映射是一一對應(yīng)的，從而基于生成樹中介數(shù)的全排列生成算法是完備的。

計(jì)算排列數(shù)由生成樹中介數(shù)還原排列數(shù)的過程實(shí)際上就是全排列生成樹的構(gòu)建過程。以生成樹中介數(shù)121為例：

（1）中介數(shù)第一位是1，說明2在1的左邊，得到21；

（2）中介數(shù)第二位為2，只能由3-1得到，說明3在1的左鄰，得到231；

（3）中介數(shù)第三位為1，只能由4-3得到，說明4在3的左鄰，得到2431.

對于任意的生成樹中介數(shù)，都通過類似的過程計(jì)算對應(yīng)的排列數(shù)。不難看出，從生成樹中介數(shù)還原排列數(shù)的時(shí)間復(fù)雜度也是 。

遞歸遞歸:設(shè)(ri)perm(X)表示每一個(gè)全排列前加上前綴ri得到的排列.當(dāng)n=1時(shí),perm(R)=(r) 其中r是唯一的元素,這個(gè)就是出口條件.

當(dāng)n>1時(shí),perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)構(gòu)成1.

voidPerm(list[],intk,intm)//k表示前綴的位置,m是要排列的數(shù)目.{if(k==m-1)//前綴是最后一個(gè)位置,此時(shí)打印排列數(shù).{for(inti=0;i