全排列數f(n)=n!(定義0!=1) 1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
這是由於算法只是考慮到了如何輸出全排列,而沒有考慮到換位是否有問題。
所以我提出了解決方案,就是換位函數修改下
如 1 2 3 換位的話 ,不應該直接 3 2 1這樣 ,
讓3和1直接換位; 而是讓3排在最前後 ,1 2 依次向後 以下介紹全排列算法四種:
(A)字典序法
(B)遞增進位制數法
(C)遞減進位制數法
(D)鄰位對換法 對給定的字符集中的字符規定了壹個先後關系,在此基礎上規定兩個全排列的先後是從左到右逐個比較對應的字符的先後。
[例]字符集{1,2,3},較小的數字較先,
這樣按字典序生成的全排列是:123,132,213,231,312,321。
[註意] 壹個全排列可看做壹個字符串,字符串可有前綴、後綴。
1)生成給定全排列的下壹個排列 所謂壹個的下壹個就是這壹個與下壹個之間沒有其他的。這就要求這壹個與下壹個有盡可能長的***同前綴,也即變化限制在盡可能短的後綴上。
[例]839647521是1--9的排列。
1—9的排列最前面的是123456789,最後面的是987654321,從右向左掃描若都是增的,就到987654321,也就沒有下壹個了。否則找出第壹次出現下降的位置。 1)由排列求中介數 在字典序法中,中介數的各位是由排列數的位決定的.中介數位的下標與排列的位的下標壹致。
在遞增進位制數法中,中介數的各位是由排列中的數字決定的。即中介數中各位的下標與排列中的數字(2—n)壹致。可看出n-1位的進位鏈。 右端位逢2進1,右起第2位逢3進1,…,
右起第i位逢i+1進1,i=1,2,…,n-1. 這樣的中介數我們稱為遞增進位制數。 上面是由中介數求排列。
由序號(十進制數)求中介數(遞增進位制數)如下:
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
在字典序法中由中介數求排列比較麻煩,我們可以通過另外定義遞增進位制數加以改進。
為方便起見,令ai+1=kn-1,i=1,2,…,n-1
(k1k2…kn-1)↑=(anan-1…a2)↑
ai:i的右邊比i小的數字的個數
在這樣的定義下,
有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個空格)
n的右邊有an個空格。
n-1的右邊有an-1個空格。
…………
2的右邊有a2個空格。
最後壹個空格就是1的位置。 在遞增進位制數法中,中介數的最低位是逢2進1,進位頻繁,這是壹個缺點。
把遞增進位制數翻轉,就得到遞減進位制數。 (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
[註意]求下壹個排列十分容易 遞減進位制數法的中介數進位不頻繁,求下壹個排列在不進位的情況下很容易。
這就啟發我們,能不能設計壹種算法,下壹個排列總是上壹個排列某相鄰兩位對換得到的。
遞減進位制數字的換位是單向的,從右向左,而鄰位對換法的換位是雙向的。 這個算法可描述如下:
對1—n-1的每壹個偶排列,n從右到左插入n個空檔(包括兩端),生成1—n的n個排列。
對1—n-1的每壹個奇排列,n從左到右插入n個空檔,生成1—n的n個排列。
對[2,n]的每個數字都是如此。
839647521
字典序法 遞增進位制法 遞減進位制法 鄰位對換法
下壹個 839651247 849617523 893647521 836947521
中介數 72642321↑ 67342221↑ 12224376↓ 10121372↓
序 號 297191 279905 340989 203393