白宇

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同037009）

全排列順序解的非遞歸算法

白宇

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同037009）

通過(guò)對(duì)數(shù)字遞增排序進(jìn)行分析，提出了一種可以按序求解全排列的非遞歸算法，并進(jìn)行了數(shù)學(xué)分析.該算法比傳統(tǒng)的遞歸算法有更高的效率和更低的空間復(fù)雜度，可以簡(jiǎn)化一些窮舉問(wèn)題的求解過(guò)程.

全排列；遞增排序；順序解；窮舉問(wèn)題

在計(jì)算機(jī)算法設(shè)計(jì)中，有一類問(wèn)題屬于NP問(wèn)題，只能通過(guò)窮舉算法求解[1-3]，例如哈密爾頓路徑問(wèn)題；或者雖不屬于NP問(wèn)題，但利用窮舉算法求解更為方便，例如N皇后問(wèn)題、約瑟夫環(huán)問(wèn)題等[1-2]。在此類問(wèn)題中，有一些類型，其求解等價(jià)于全排列問(wèn)題的求解[1-3]，例如N皇后問(wèn)題.通過(guò)全排列求解可以簡(jiǎn)化原問(wèn)題，由于全排列的時(shí)間復(fù)雜度為O（n!），當(dāng)問(wèn)題規(guī)模較小時(shí)，具有實(shí)用價(jià)值。

傳統(tǒng)求解全排列的算法有兩種：一是通過(guò)逐一交換每個(gè)位置的不同元素；二是在附加空間中逐一增加源序列中不同位置的每個(gè)元素[4-5]。這兩種算法均為遞歸算法，需消耗較大的遞歸?？臻g和輔助空間。從數(shù)字遞增排序的角度出發(fā)，提出了一種非遞歸求解全排列的算法，其效率較高，無(wú)需遞歸棧空間，且可求得全排列的順序解。

1 算法設(shè)計(jì)

求解全排列有兩種思路：一是直接對(duì)元素進(jìn)行排列；二是對(duì)位置進(jìn)行排列，然后轉(zhuǎn)換為元素[6]。由于待排列的元素可以是各種類型，可能不便對(duì)其進(jìn)行運(yùn)算或比較大小，因此第二種思路適應(yīng)性更強(qiáng)，本文所述算法即基于第二種思路設(shè)計(jì)。

設(shè)源序列e中各元素的位置從左到右依次為：

根據(jù)全排列的定義，則對(duì)e的全排列求解便轉(zhuǎn)換為對(duì)數(shù)字1到n可構(gòu)成的所有數(shù)字遞增排序的求解。由于該n個(gè)數(shù)字均不相等，因此，其構(gòu)成的全排列可由小到大表示為n!個(gè)數(shù)字。

顯然，（1）式所構(gòu)成的數(shù)字可表示為：

此時(shí)，（2）式是所有可構(gòu)成的數(shù)字中最小的，將（2）式的數(shù)字翻轉(zhuǎn)，得：

此時(shí)，（3）式是所有可構(gòu)成的數(shù)字中最大的。對(duì)序列e求全排列順序解的過(guò)程，即是求從（2）式到（3）式的數(shù)字遞增排序的過(guò)程。

將（1）式表示為p：

從（4）式的排列開始可由4個(gè)步驟找到大于（4）式的最小排列，即下一個(gè)排列：

step1從排列的尾部（最右邊）開始，找出第一個(gè)比右邊相鄰數(shù)字小的索引j（j從首部開始計(jì)算），即j=max{i|pi＜pi+1}；

step2在pj右邊的數(shù)字中，找出所有比pj大的數(shù)字中最小的數(shù)字的索引k，即 k=max{i|pi＞pj}；由于pj右邊的數(shù)字是從右至左遞增的，因此k是所有大于pj的數(shù)字中索引最大的；

step3交換pj與pk；

step4將pj+1...pk-1，pj，pk+1...pn翻轉(zhuǎn)得到 p的下一個(gè)排列p′：

所述算法通過(guò)不斷重復(fù)上述過(guò)程，直到在step1中查找j失敗，此時(shí)已經(jīng)得到了（3）式所表示的最大排列。

上述步驟的正確性證明如下：

定理1 數(shù)字p逐位表示如（4）式，其中pj+1＞…＞pk-1＞pk＞pk+1＞…＞pn且 pj＜pj+1，pk＞pj，且 pk+1＜pj，p′表示如（5）式，則p′為大于p的最小整數(shù)。

證明首先證明p′＞p，利用反證法。

設(shè)p′≤p，有（5）式≤（4）式，則pk≤pj，與命題相悖，故p′＞p；

其次證明p′為大于p的最小整數(shù)，同樣利用反證法。

設(shè)?p″，p″＜p′且p″＞p，則?m，使得pm＜pk且pm＞pj，同時(shí)：

因?yàn)?pm＜pk，且 pj+1＞…＞pk-1＞pk＞pk+1＞…＞pn且 pj＜pj+1，根據(jù)關(guān)系的傳遞性得：

又因?yàn)閜m＞pj，且pk＞pj，pk+1＜pj，根據(jù)關(guān)系的傳遞性，有pm＞pk+1，根據(jù)（6）式得：

由（7）式和（8）式得：

（9）式與假設(shè)相悖，即無(wú)法找到pm，因此pm不存在，故p′為大于p的最小整數(shù)，證畢。

例1 24310是位置編號(hào)0～4的一個(gè)排列，求它下一個(gè)排列。

解step1從右至左找出排列中第一個(gè)比右邊相鄰數(shù)字小的數(shù)字2，即j=1，pj=2；

step2在該數(shù)字后的數(shù)字中找出比2大的數(shù)中最小的數(shù)字3，即k=3，pk=3；

step3將2與3交換得到34210；

step4將原來(lái)2（當(dāng)前3）后面的所有數(shù)字翻轉(zhuǎn)，即翻轉(zhuǎn)4210，得30124。

求得24310的下一個(gè)排列為30124。

2 算法分析

2.1 時(shí)間復(fù)雜度

首先，需構(gòu)建元素位置的索引數(shù)組。

設(shè)每個(gè)元素的操作次數(shù)為1，則：

其次，step1所描述的查找pj的過(guò)程。由于子序列pj，pj+1...pk-1，pk，pk+1...pn的長(zhǎng)度未知，不能采用二分查找算法[2-3]，故采用順序查找算法，其最壞情況時(shí)，操作次數(shù)與（10）式相同，即為n。

再次，step2所描述的查找pk的過(guò)程，同樣采用順序查找，其操作次數(shù)與（10）式相同，即為n。

最后，step4所描述的翻轉(zhuǎn) pj+1...pk-1，pj，pk+1...pn的過(guò)程，采用由序列兩端向中間逐個(gè)交換元素的辦法，因?yàn)槊看谓粨Q涉及3次賦值操作，則：

已知n個(gè)數(shù)的全排列個(gè)數(shù)為n![1-3]，所以，根據(jù)（10）式和（11）式，可知算法時(shí)間復(fù)雜度為：

2.2 空間復(fù)雜度

根據(jù)“算法設(shè)計(jì)”中的描述，本文所述算法的輔助空間分為兩類。其一，表示元素位置的整型數(shù)據(jù)空間，其長(zhǎng)度為n；其二，用于交換位置數(shù)據(jù)的輔助空間，其長(zhǎng)度為1。因此，算法的空間復(fù)雜度為O（n）.相對(duì)遞歸算法而言，空間復(fù)雜度由O（n!）降為O（n），且每個(gè)空間僅為32Bit的整形數(shù)據(jù)（由于元素?cái)?shù)量較少可使用無(wú)符號(hào)byte類型，即最大表示28=256個(gè)元素位置）。

3 算法描述

1）sort（index），根據(jù)定理1，轉(zhuǎn)換位置數(shù)組index

到下一個(gè)排列，如果成功則返回true，否則返回

false。其中index數(shù)組的長(zhǎng)度為length。

1.length-2→j

2.if j＜0 or index[j]≤index[j+1]then go 5

3.j-1→j

4.go 2

5.if j＜0 then return flase

6.length-1→k

7.if index[k]≥index[j]then go 10

8.k-1→k

9.go 7

10.index[j]?index[k]

11.j+1→j

12.length-1→k

13.if j≥k then go 18

14.index[j]?index[k]

15.j+1→j

16.k-1→k

17.go 13

18.return true

2）perm（arr），對(duì)任意類型的數(shù)組arr進(jìn)行全排列。其中數(shù)組arr、index和result的長(zhǎng)度相等，均為length。

1.0→i

2.if i≥length then go 6

3.i→index[i]

4.i+1→i

5.go 2

6.0→i

7.if i≥length then go 11

8.arr[index[i]]→result[i]

9.i+1→i

10.go 7

11.output result

12.if sort（index）then go 6

4 算法實(shí)現(xiàn)

使用JavaScript（ECMAScript）實(shí)現(xiàn)，本文僅給出sort和perm算法主體部分的實(shí)現(xiàn)，其余部分不再贅述。

function sort（index）{

for（var j=index.length-2；j＞=0＆＆index[j]＞index[j+1]；j--）{}

if（j＜0）return false；

5 結(jié)語(yǔ)

所述算法采用非遞歸設(shè)計(jì)，不需要保護(hù)和恢復(fù)現(xiàn)場(chǎng)，其效率較遞歸算法要高；由于無(wú)需遞歸?？臻g，其空間復(fù)雜度較遞歸算法要低；并且能順序求解全排列，在窮舉算法中便于量化分析窮舉過(guò)程。綜上所述，該算法在求解一些窮舉問(wèn)題時(shí)具有實(shí)用價(jià)值，可替代傳統(tǒng)全排列的遞歸求解算法。

[1]Robert Sedgewick，Kevin Wayne.Algorithms Fourth Edi-tion[M].New Jersey：Pearson Education，2012：101-181.

[2]Torben Hagerup.Algorithm Theory-Swat2004[M].New York：Springer Verlag，2004：99-155.

[3]Bergin，Joseph.Data Structure Programming[M].New York：Springer Verlag，2005：78-105.

[4]Cormen，Thomas H.（EDT）/Leiserson，Charles E./Rivest，etal.Introduction To Algorithms[M].Massachusetts：Mit Pr，2005：166-192.

[5]Donald Knuth.The Artof Computer Programming，Volume 4[M].US：Addison-Wesley，2005：62-76.

[6]Miklos Bona.Combinatorics of Permutations[M].UK：Chapman Hall-CRC，2004：125-137.

Non－recursive A lgorithm of F ull P ermutation O rdinal S olution

BAIYu
（School of Mathematics＆Computer Science，ShanxiDatong University，Datong Shanxi，037009）

Analyzed by ascending sort of digital，this paper designed non－recursive algorithm of ordinal solving the full permutation，and itsmathematical analysis.The algorithm has higher efficiency and lower space complexity than conventional recursive algorithms，it can simplify the solution procedure for exhaustive problem.

full permutation；ascending sort；ordinal solution；exhaustive problem 〔責(zé)任編輯 高?！?/p>

TP312.12

A

1674－0874（2013）06－0009－03

2013－08－08

白宇（1976-），男，山西大同人，碩士，講師，研究方向：圖論算法，并行算法，云計(jì)算。