全排列算法的理解與實現(xiàn)（遞歸+字典序）

一、全排列的概念

排列：

??從n個數(shù)中選取m（m<=n）個數(shù)按照一定的順序進行排成一個列赃春，叫作從n個元素中取m個元素的一個排列燕酷。不同的順序是一個不同的排列喊巍。從n個元素中取m個元素的所有排列的個數(shù)鼎姊，稱為排列數(shù)骡和。

全排列：

??從n個元素取出n個元素的一個排列，稱為一個全排列相寇。全排列的排列數(shù)公式為 $n!$

時間復雜度：

??n個數(shù)的全排列有n!種慰于，每一個排列都有n個數(shù)據(jù)，所以輸出的時間復雜度為O(n*n!)裆赵，呈指數(shù)級，無法處理大型數(shù)據(jù)跺嗽。

二战授、遞歸的全排列算法

算法思路：

假設我們要對1，2桨嫁，3植兰，4四個數(shù)進行全排列，過程如下：
??(a)首先保持1不變璃吧，對2楣导，3，4全排列畜挨；
??(b)保持2不變筒繁，對3，4全排列巴元；
??(c)保持3不變毡咏，對4全排列，4的排列只有一種逮刨。得到1呕缭，2，3，4
??(d)然后3不能不變了恢总，繼續(xù)保持2不變迎罗，3，4互換得到1片仿，2纹安，4，3
??(e)以1滋戳，2打頭的排列完成钻蔑，接下來把3換到2的位置，繼續(xù)(c)奸鸯、(d)的操作
? ……
?得到1咪笑，3，2娄涩，4
???1窗怒，3，4蓄拣，2
???1扬虚，4，3球恤，2
???1辜昵，4，2咽斧，3
??因此得到以1打頭的全部排序堪置，以此類推，得到以2张惹，3舀锨，4打頭的排序，得到全排序宛逗。

將以上過程總結成一個遞歸算法：

??任取一個數(shù)打頭坎匿，對后面n-1個數(shù)進行全排序，要求n-1個數(shù)的全排序雷激，則要求n-2個數(shù)的全排序……直到要求的全排序只有一個數(shù)替蔬，找到出口。

偽代碼：

m到n的全排序
Permutation(m,n){
if:全排列只有一個數(shù)屎暇，輸出排列
  else: 
    for{i=m;i<n;i++}{//i遍歷第m~n個數(shù)进栽，每次以a[i]所存的數(shù)值為打頭的數(shù)
        swap(a[m],a[i]);//把要打頭的數(shù)放到最開頭的位置（即m所在的位置）
        Permutation(m+1,n);//遞歸
        swap(a[m],a[i]);//為避免重復排序，每個數(shù)打頭結束后都恢復初始排序,防止重復的方法很多恭垦，不止這一種
     }
}

從第m個元素到第n個元素的全排列代碼：

void Permutation(int a[],int m,int n){
    if(m==n){
        cout<<a[0];
        for(int i=1;i<n;i++){
            cout<<" "<<a[i];
        }
        cout<<endl;
    }
    else {
        for(int i=m;i<n;i++){
            int temp=a[m];
            a[m]=a[i];
            a[i]=temp;
            Permutation(a,m+1,n);
            temp=a[m];
            a[m]=a[i];
            a[i]=temp;
        }
    }
}

三快毛、字典序

定義：對于一個序列a1,a2,a3,a4,a5....an的兩個排列b1,b2,b3,b4,b5...bn和c1,c2,c3,c4,c5...cn, 如果它們的前k項一樣格嗅，且c(k +1)> b(k+1),則稱排列c位于排列b的后面。如1唠帝，2屯掖，3刚梭，4的字典序排在1棍掐，2，4叹括，3的前面（k=2）瀑晒，1绍坝，3，2苔悦，4的字典序在1轩褐，2，3玖详，4(k=1)的后面把介。
??顯然，對一個無重復元素的集合蟋座，它每種排序的字典序位置不同拗踢。按字典序進行全排列，使排列變得有序向臀。
e.g.按字典序排列1巢墅，2，3的結果：
??1券膀，2君纫，3
??1，3三娩，2
??2庵芭，1妹懒，3
??2雀监，3，1
??3眨唬，1会前，2
??3，2匾竿，1
思路：
??該算法的關鍵在于瓦宜，找到緊跟在某一個排列后面的字典序。證明過程有點繞岭妖，我就講講我是如何通俗的理解這個算法的（舉的例子可能不太嚴謹）临庇。
??假設有一排列 $a_1,a_2,a_3...a_n$ 反璃，顯然，若 $a_n> a_{n-1}$ 假夺，則 $a_1,a_2,a_3...a_n,a_{n-1}$ 是它后面的字典序淮蜈。
??若 $a_n< a_{n-1}$ ，則需不斷向前尋找已卷，直到找到 $a_{m+1} > a_m$
我們可以看到梧田， $a_{m+1},...,a_n$ 是降序排列，是排序中最大的情況（不理解的想象一下用1~9組成的各位不重復的最大數(shù)是987654321）侧蘸。

字典序.jpg

??想象有個十進制數(shù)19裁眯，我們來看一下要找到比它大的數(shù)——20，需要做哪些事情：由于個位數(shù)是9讳癌，已是最大情況穿稳，所以我們要將十位稍微調大一點，然后把個位改到最小析桥，便得到緊跟著19后面的數(shù)司草。
??因此，仿照上面的例子泡仗，我們做以下操作：從a_m+1,...,a_n中找到比a_m大的最小項埋虹，和a_m互換位置，然后再將新的a_m+1,...,a_n升序排列（將新的a_m+1,...,a_n改到最小娩怎，就如十位數(shù)20個位的0）搔课，這樣得到的字典序便是緊挨著排列的后一個字典序。

字典序算法的實現(xiàn)：

bool Next_Permutation(int a[], int n){
    int i,m,temp;
    for(i = n-2;i >= 0;i--){
        if(a[i+1] > a[i]) break;
    }
    if(i < 0) return false;
    m = i;
    i++;
    for(;i<n;i++){
        if(a[i] <= a[m]){
            i--;
            break;
        }
        else if(i==n-1) break;
        }
    temp=a[m];
    a[m]=a[i];
    a[i]=temp;
    sort(a+m+1,a+n);
    cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];
    }
    cout<<endl;
    return true;
}

void dict_Permutation(int a[],int n){
    sort(a,a+n);
    cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];
    }
    cout<<endl;
    while(Next_Permutation(a,n));
}

利用STL中的next_permutation()函數(shù)寫全排列

??C++的STL真是個令人偷懶的好東西截亦。algorithm中提供了next_permutation模版函數(shù)爬泥，可直接代替上面的Next_Permutation（）函數(shù)，不過這個函數(shù)沒有輸出崩瓤，而是直接把數(shù)組變成了它的下一個字典序袍啡。

利用STL求全排列代碼：

void stl_Permutation(int a[],int n){
    int b[n];
    for(int i=0;i<n;i++){
        b[i]=a[i];
    }
    sort(b,b+n);
    do{
        cout<<b[0];
        for(int i=1;i<n;i++) cout<<" "<<b[i];
        cout<<endl;
    }while(next_permutation(b,b+n));
}

比較：

??在處理元素相同情況時，字典序算法不會重復輸出却桶。而一開始給出的遞歸算法會重復（要使之不重復境输，應在交換之前判斷相鄰著的兩個數(shù)是否相同，如果相同颖系，則不交換）嗅剖。但是字典序算法把原來數(shù)組改變了，若需要保留原數(shù)組可以拷貝一個數(shù)組b嘁扼，在新數(shù)組內操作信粮。