白宇

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

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

白宇

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

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

全排列；遞增排序；順序解；窮舉問題

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

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

1 算法設計

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

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

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

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

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

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

將（1）式表示為p：

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

step1從排列的尾部（最右邊）開始，找出第一個比右邊相鄰數(shù)字小的索引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翻轉得到 p的下一個排列p′：

所述算法通過不斷重復上述過程，直到在step1中查找j失敗，此時已經(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，利用反證法。

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

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

設?p″，p″＜p′且p″＞p，則?m，使得pm＜pk且pm＞pj，同時：

因為 pm＜pk，且 pj+1＞…＞pk-1＞pk＞pk+1＞…＞pn且 pj＜pj+1，根據(jù)關系的傳遞性得：

又因為pm＞pj，且pk＞pj，pk+1＜pj，根據(jù)關系的傳遞性，有pm＞pk+1，根據(jù)（6）式得：

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

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

例1 24310是位置編號0～4的一個排列，求它下一個排列。

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

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

step3將2與3交換得到34210；

step4將原來2（當前3）后面的所有數(shù)字翻轉，即翻轉4210，得30124。

求得24310的下一個排列為30124。

2 算法分析

2.1 時間復雜度

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

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

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

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

最后，step4所描述的翻轉 pj+1...pk-1，pj，pk+1...pn的過程，采用由序列兩端向中間逐個交換元素的辦法，因為每次交換涉及3次賦值操作，則：

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

2.2 空間復雜度

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

3 算法描述

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

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

false。其中index數(shù)組的長度為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），對任意類型的數(shù)組arr進行全排列。其中數(shù)組arr、index和result的長度相等，均為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 算法實現(xiàn)

使用JavaScript（ECMAScript）實現(xiàn)，本文僅給出sort和perm算法主體部分的實現(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 結語

所述算法采用非遞歸設計，不需要保護和恢復現(xiàn)場，其效率較遞歸算法要高；由于無需遞歸?？臻g，其空間復雜度較遞歸算法要低；并且能順序求解全排列，在窮舉算法中便于量化分析窮舉過程。綜上所述，該算法在求解一些窮舉問題時具有實用價值，可替代傳統(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 〔責任編輯 高?！?/p>

TP312.12

A

1674－0874（2013）06－0009－03

2013－08－08

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