非有序全排列生成算法

作者：goal00001111（高粱）

 

我曾經寫過一篇《有序全排列生成算法》，介紹了五種生成有序全排列的方法，在該文的末尾，我計劃再寫一篇姊妹篇《非有序全排列生成算法》，由于各種原因，一直遲遲未動筆，前幾天學習數據結構“棧”的時候，碰到一個有趣的問題“列車出棧序列”，其中有一種解法需要用到非有序全排列，所以決定先寫好本文，再總結該問題。

生成非有序全排列的算法很多，有普通遞歸算法，循環移位法，鄰位對換法，需要中介數的遞增進位排列生成算法，遞減進位排列生成算法和循環左移排列生成算法等。

我們先看最簡單的普通遞歸算法，它的原理是：

如果用P表示n個元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前綴i的排列，那么，n個元素的排列可遞歸定義為：

如果n=1，則排列P只有一個元素i

如果n>1，則排列P由排列(i)Pi構成（i=1、2、....、n-1）。

根據定義，容易看出如果已經生成了k-1個元素的排列，那么，k個元素的排列可以在每個k-1個元素的排列Pi前添加元素i而生成。

例如2個元素的排列是 1 2和2 1，對每個元素而言，p1是2 3和3 2，

在每個排列前加上1即生成1 2 3和1 3 2兩個新排列，p2和p3則是1 3、3 1和1 2、2 1，按同樣方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。

主要代碼如下：

/*

函數名稱：Permutation

函數功能：普通遞歸算法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(int n)

{

    int *a = new int[n];//用來存儲n個自然數

    for (int i=0; i<n; i++) //存儲全排列的元素值

        a[i] = i + 1;

   

    Recursion(a, n, n-1); //調用遞歸函數     

    delete []a;

}

 

/*

函數名稱：Recursion

函數功能：遞歸輸出n個數的所有全排列

輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數的數組

          int n：數組a[]的長度

          int k：正在處理的k個元素所組成的排列

輸出變量：無

*/

void Recursion(int a[], int n, int k)

{

    if (k == 0) //排列只有一個元素a[k]，直接輸出

        Print(a, n);

    else

    {

        int temp;

        for (int i=0; i<=k; i++) //窮舉，依次讓第k個元素與前面的元素交換

        {

            temp = a[i];

            a[i] = a[k];

            a[k] = temp;

           

            Recursion(a, n, k-1); //遞歸生成k-1個元素的全排列

           

            temp = a[i]; //再換回來

            a[i] = a[k];

            a[k] = temp;

        }

    }

}

 

void Print(int a[], int n)

{

    for (int i=0; i<n; i++)

        cout << a[i];

    cout << endl;

}

 

循環移位法是一種很容易理解的非有序全排列算法，它的原理是：如果已經生成了k-1個元素的排列，則在每個排列后添加元素k使之成為k個元素的排列，然后將每個排列循環左移（右移），每移動一次就產生一個新的排列。

例如2個元素的排列是1 2和2 1。在1 2 后加上3成為新排列1 2 3，將它循環左移可再生成新排列2 3 1、3 1 2，

同樣2 1 可生成新排列2 1 3、1 3 2和3 2 1。

代碼也和簡單，使用了遞歸窮舉思想，我生成了一個循環左移的算法，有興趣的讀者可以自己生成一個循環右移的算法。

/*

函數名稱：Permutation

函數功能：全排列循環移位法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(int n)

{

    unsigned int *a = new unsigned int[n];//用來存儲n個自然數

    for (int i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數量

    {

        a[i] = i + 1;

    }

   

    Recursion(a, n, 1);

   

    delete []a;

}

/*

函數名稱：Recursion

函數功能：循環左移遞歸輸出n個數的所有全排列

輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數的數組

          int n：數組a[]的長度

          int k：正在處理的k個元素所組成的排列

輸出變量：無

 

*/

void Recursion(unsigned int a[], int n, int k)

{

    if (k > n)

        Print(a, n);

    else

    {

        int temp;

        for (int i=0; i<k; i++)//循環左移

        {

            temp = a[0];

            for (int j=1; j<k; j++)

                a[j-1] = a[j];

            a[k-1] = temp;

            

            Recursion(a, n, k+1);

        }

    }

}

 

一個能夠快速生成全排列的算法叫做鄰位對換法，它之所以較快，是因為鄰位對換法中下一個排列總是上一個排列某相鄰兩位對換得到的，只需一步，就可以得到一個新的全排列，而且絕不重復，但是由于每將n從一端移動到另一端后，就需要遍歷排列2次，來尋找最大的可移數m，所以速度得到了限制。它的原理是：

[n]的全排列可由[n-1]的全排列生成：

給定[n-1]的一個排列п,將n 由最右端依次插入排列п ，即得到n個[n]的排列： 

p1 p2…pn-1n

p1 p2…npn-1

np1 p2…pn-1

對上述過程，一般地，對i，將前一步所得的每一排列重復i次，然后將i由第一排的最后往前移，至最前列，正好走了i次,下一個接著將i放在下一排列的最前面，然后依次往后移，一直下去即得i元排列。

考慮{1,2…n}的一個排列，其上每一個整數都給了一個方向，如果它的箭頭所指的方向的鄰點小于它本身，我們稱整數k是可移的。

顯然1永遠不可移，n除了以下兩種情形外，它都是可移的:

(1) n是第一個數，且其方向指向左側

(2) n是最后一個數，且其方向指向右側

于是，我們可按如下算法產生所有排列：

1，開始時：存在排列123…n，除1外，所有元素均可移，即方向都指向左側。

2，當最大元素n可移動時，將其從一端依次移動到另一端，即可得到n-1個全排列；當n移動到某一端后，不能再移動，此時尋找最大的可移數m，將m與其箭頭所指的鄰數互換位置，這樣就又得到一個新的全排列；將所得新排列中所有比m大的數p的方向調整，即改為相反方向，這樣使得n又成了可移數。

3，重復第2步直到所有的元素都不能移動為止。

以4個元素的排列為例，首先生成全排列1 2 3 4；

找到最大的可移數4，將4與其箭頭所指的鄰數互換位置，可以生成3個新排列：

1 2 4 3   1 4 2 3   4 1 2 3

因為沒有比4更大的數p，所以無需調整p的方向。最大數4到了最左邊后，由于其方向指向左側，所以4不能再移動。

接下來尋找最大的可移數3，將3與其箭頭所指的鄰數2互換位置，可以得到新排列：4 1 3 2；

然后將所得排列中比3大的數4的方向調整，使得4可以移動，重新成為最大的可移數，將4與其箭頭所指的鄰數互換位置，可以生成3個新排列：

1 4 3 2   1 3 4 2   1 3 2 4

此時最大數4到了最右邊，又因為其方向指向右側，所以4不能再移動；于是我們尋找最大的可移數3，將3與其箭頭所指的鄰數1互換位置，可以得到新排列：3 1 2 4；

然后將所得排列中比3大的數4的方向調整，使得4可以移動，重新成為最大的可移數，將4與其箭頭所指的鄰數互換位置，可以生成3個新排列：

3 1 4 2   3 4 1 2   4 3 1 2

如此循環，直到所有的數都不能移動，即可求出全部排列。最后得到的一個全排列為：2 1 3 4，此時2指向左側，1，3，4均指向右側。

根據上述算法分析，使用一個輔助數組來存儲各個元素的指向，我們可以得到代碼如下：

/*

函數名稱：Permutation

函數功能：排列鄰位對換法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(int n)

{

    int  *a = new int[n];  //用來存儲n個自然數

    bool *p = new bool[n]; //用來存儲n個元素的指向：向左為false，向右為true

    for (int i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數量

    {

        a[i] = i + 1;

        p[i] = false; //開始均指向左側

    }

   

    do

    {

        Print(a, n); //輸出第一個全排列

        if (n == a[n-1])//若n在最右側，將其逐次與左側的元素交換，得到n - 1個新的排列

        {

            for (int i=n-1; i>0; i--)

            {

                int  temp = a[i]; a[i] = a[i-1]; a[i-1] = temp;

                bool flag = p[i]; p[i] = p[i-1]; p[i-1] = flag;

                Print(a, n);

            }

        }

        else //若n在最左側，將其逐次與右側的元素交換，得到n - 1個新的排列

        {

            for (int i=1; i<n; i++)

            {

                int temp = a[i]; a[i] = a[i-1]; a[i-1] = temp;

                bool flag = p[i]; p[i] = p[i-1]; p[i-1] = flag;

                Print(a, n);

            }

        }

    } while (Move(a, p, n));

   

    delete []a;

    delete []p;

}

 

/*

函數名稱：Move

函數功能：尋找最大可移數，可移數m，將m與其箭頭所指的鄰數互換位置，

          并將所得新排列中所有比m大的數p的方向調整

輸入變量：int a[]：存儲了1，2，3，...，n共n個自然數的數組

          bool p[]：存儲了n個元素的指向的數組：向左為false，向右為true

          int n：數組a[]的長度

輸出變量：排列中存在最大可移數，則做了相關操作后返回真，否則直接返回假

*/

bool Move(int a[], bool p[], int n)

{

    int max = 1;

    int pos = -1;

   

    for (int i=0; i<n; i++)

    {

        if (a[i] < max)

            continue;

        if ((p[i] && i < n-1 && a[i] > a[i+1]) || //指向右側 

            (!p[i] && i > 0 && a[i] > a[i-1]))    //指向左側

        {

            max = a[i];

            pos = i;

        }

    }

   

    if (pos == -1) //都不能移動

        return false;

  

    //與其箭頭所指的鄰數互換位置

    if (p[pos]) //指向右側

    {

        int  temp = a[pos]; a[pos] = a[pos+1]; a[pos+1] = temp;

        bool flag = p[pos]; p[pos] = p[pos+1]; p[pos+1] = flag;

    }

    else //指向左側

    {

        int  temp = a[pos]; a[pos] = a[pos-1]; a[pos-1] = temp;

        bool flag = p[pos]; p[pos] = p[pos-1]; p[pos-1] = flag;

    }

   

    //將所得排列中所有比max大的數p的方向調整

    for (int i=0; i<n; i++)   

    {

        if (a[i] > max)

            p[i] = !p[i];

    }

   

    return true;

}

 

遞增進位排列生成算法是需要設置中介數的一種算法，它的映射和還原方法如下：

映射方法：將原排列按照從9到2的順序，依次查看其右側比其小的數字有幾個，個數就是中介數的一位。例如對于原排列839647521。9的右側比9小的數字有6個，8的右側比8小的數字有7個，7的右側比7小的數字有3個，……2的右側比2小的數字有1個。最后得到遞增進制中介數67342221。（此中介數加上100的遞增進制數4020得到新的中介數67351311）

還原方法：我們設新中介數的位置號從左向右依次是9、8、7、6、5、4、3、2。在還原前，畫9個空格。對于每一個在位置x的中介數y，從空格的右側向左數y個未被占用的空格。在第y+1個未占用的空格中填上數字x。重復這個過程直到中介數中所有的位都被數完。最后在余下的最后一個空格里填上1，完成新排列的生成。以新中介數67351311為例，我給出了詳細的恢復步驟。其中紅色數字代表新填上的數字。最后得到新排列869427351。

新中介數當前位	新排列數	備注
初始		在還原前，畫9個空格
6	9	從右向左數6個空格，第7個空格里填“9”
7	8   9	從右向左數7個空格，第8個空格里填“8”
3	8   9     7	從右向左數3個空格，第4個空格里填“7”
5	8 6 9     7      9	從右向左數5個空格，第6個空格里填“6”
1	8 6 9     7   5  9	從右向左數1個空格，第2個空格里填“5”
3	8 6 9 4   7   5  7	從右向左數3個空格，第4個空格里填“4”
1	8 6 9 4   7 3 5  7	從右向左數1個空格，第2個空格里填“3”
1	8 6 9 4 2 7 3 5  7	從右向左數1個空格，第2個空格里填“2”
最后補位	8 6 9 4 2 7 3 5 1	余下的空格填“1”

 

    我們設原中介數為0，然后讓中介數加上遞增序號1，根據上文將的方法得到新的中介數，最后還原新中介數，得到一個全排列。重復上述過程就可以得到所有所有的全排列。

主要代碼如下：

/*

函數名稱：Permutation

函數功能：遞增進位排列生成算法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!

    p[0] = 1;

    for (int i=1; i<n; i++)

    {

        p[i] = (i + 1) * p[i-1]; //cout << p[i] << "  ";

    }

 

    int *b = new int[n];      //用來存儲新的全排列

    int *yShe = new int[n-1]; //將原中介數加上序號i的遞增進位制數得到新的映射

    int *diZ = new int[n-1];  //用來存儲序號i的遞增進位制數，設所有元素的初值為0

    for (int i=0; i<n-1; i++)

    {

        diZ[i] = yShe[i] = 0;

    }

   

    diZ[n-2] = 1; //存儲序號1，表示每次遞增1

    for (int c=0; c<p[n-1]; c++)

    {

        DiZYingShe(yShe, diZ, n); //每次遞增1后得到得到新的映射

       

        for (int i=0; i<n; i++) //新的全排列空格初始化

            b[i] = 0;

       

        int num = n;

        for (int j=0; j<n-1; j++) //獲取前n-1個數字

        {

            int s = 0;

            int k = n - 1;

            while (s < yShe[j])

            {

                if (b[k] == 0) //該處未填數字

                    s++;

                k--;

            }

            while (b[k] != 0) //跳過已填數字

                k--;

            b[k] = num--;

        }

        for (int i=0; i<n; i++)//填充最后一個數字1

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

        Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diZ;

    delete []yShe;

}

 

/*

函數名稱：DiZYingShe

函數功能：遞增進位排列生成算法的加法運算：yShe[] += dZJ[]

輸入變量：int yShe[]：原遞增進制中介數；

          int diZ[]：遞增進制數加數

          int len：最大自然數n的值

輸出變量：int yShe[]：新的增進制中介數

*/

void DiZYingShe(int yShe[], int diZ[], int n)

{

    int pos = n - 2;

    int r = 0;

    while (pos >= 0)

    {

        yShe[pos] += diZ[pos] + r;

        if (yShe[pos] >= n - pos)

        {

            yShe[pos] -= n - pos;

            r = 1;

        }

        else

            r = 0;

        pos--;

    }

}

 

遞減進位制排列生成算法和遞增進位制排列生成算法的原理很相似，都需要一個先映射一個中介數，我們設原中介數為0，讓中介數加上遞增序號1后再還原中介數，就得到一個全排列。

    遞減進位制和遞增進位制的映射方法，以及還原方法都剛好相反。

映射方法：遞減進位制的映射方法剛好和遞增進位制相反，即按照從9到2的順序，依次查看其右側比其小數字的個數。但是，生成中介數的順序不再是從左向右，而是從右向左。生成的遞減進制中介數剛好是遞增進位排列生成算法得到中介數的鏡像。例如839647521的遞減進制中介數就是12224376。（此中介數加上 100的遞減進制數131后得到新中介數12224527）

還原方法：遞減進位制中介數的還原方法也剛好和遞增進位制中介數相反。遞增進位制還原方法是按照從中介數最高位（左側）到最低位（右側）的順序來填數。而遞減僅位置還原方法則從中介數的最低位向最高位進行依次計數填空。例如對于新中介數12224527，我給出了詳細的還原步驟。紅色代表當前正在填充的空格。最終得到新排列 397645821。

新中介數當前位	新排列數	備注
初始		在還原前，畫9個空格
7	9	從右向左數7個空格，第8個空格里填“9”
2	9         8	從右向左數2個空格，第3個空格里填“8”
5	9 7       8	從右向左數5個空格，第6個空格里填“7”
4	9 7 6     8    9	從右向左數4個空格，第5個空格里填“6”
2	9 7 6   5 8    9	從右向左數2個空格，第3個空格里填“5”
2	9 7 6 4 5 8    7	從右向左數2個空格，第3個空格里填“4”
2	3 9 7 6 4 5 8    7	從右向左數2個空格，第3個空格里填“3”
1	3 9 7 6 4 5 8 2  7	從右向左數1個空格，第2個空格里填“2”
最后補位	3 9 7 6 4 5 8 2 1	余下的空格填“1”

 

主要代碼如下：

/*

函數名稱：Permutation

函數功能：遞減進位排列生成算法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!

    p[0] = 1;

    for (int i=1; i<n; i++)

    {

        p[i] = (i + 1) * p[i-1]; //cout << p[i] << "  ";

    }

 

    int *b = new int[n];//用來存儲新的全排列

    int *yShe = new int[n-1]; //將原中介數加上序號i的遞減進位制數得到新的映射

    int *diJ = new int[n-1];

    for (int i=0; i<n-1; i++)

    {

        diJ[i] = yShe[i] = 0;

    }

   

    diJ[n-2] = 1;

    for (int c=0; c<p[n-1]; c++)

    {

        DiJYingShe(yShe, diJ, n);  //每次遞增1

       

        for (int i=0; i<n; i++) //新的全排列空格初始化

            b[i] = 0;

       

        int num = n;

        for (int j=n-2; j>=0; j--) //獲取前n-1個數字

        {

            int s = 0;

            int k = n - 1;

            while (s < yShe[j])

            {

                if (b[k] == 0) //該處未填數字

                    s++;

                k--;

            }

            while (b[k] != 0) //跳過已填數字

                k--;

            b[k] = num--;

        }

        for (int i=0; i<n; i++)//填充最后一個數字1

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

    Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diJ;

    delete []yShe;

}

 

/*

函數名稱：DiJYingShe

函數功能：遞減進位排列生成算法的加法運算：yShe[] += dZJ[]

輸入變量：int yShe[]：原遞減進制中介數；

          int diJ[]：遞減進制數加數

          int n：最大自然數n的值

輸出變量：int yShe[]：新的遞減進制中介數

*/

void DiJYingShe(int yShe[], int diJ[], int n)

{

    int pos = n - 2;

    int r = 0;

    while (pos >= 0)

    {

        yShe[pos] += diJ[pos] + r;

        if (yShe[pos] >= pos + 2)

        {

            yShe[pos] -= pos + 2;

            r = 1;

        }

        else

            r = 0;

        pos--;

    }

}

 

循環左移排列生成算法

映射方法：循環左移排列生成算法與遞減進位排列生成算法非常相似，同樣是在原始排列中找到比當前數字小的數字個數。只不過循環左移使用的是左循環搜索法，而不是遞減進位法使用的右側搜索。所謂左循環搜索法是指從起始數字開始向左搜索，如果到了左邊界還沒有發現終止數字，則從右邊界開始繼續尋找，直到終止數字被發現。

圖中展示了839647521種以開始數字為6，

結束數字為5和開始數字為7，結束數字為6的

左循環搜索區間，注意開始和結束數字是不包括

在區間內的。

具體到循環左移的排列生成法的映射方法，

就是要為每一個數字確定這樣一個區間。方法是

以從9到2的順序依次產生中介數中的數字，中介數

從右向左產生（即原排列的9產生的數字放到中介數右數第一位，8產生的數字放到中介數右數第二位，以此類推。這樣才能得到遞減進位制數）。對于9，產生的中介數字依然是9的右邊比9小的數字的個數。但是從8開始一直到2中的每一個數i，都是要做一個以i+1為開始數字，i為結束數字的左循環區間，并看這個左循環區間中比i小的數字的個數。例如對于排列839647521，9的右側比9小的數字有6個；9到8的左循環區間比8小的數字有1個；8到7的左循環區間比7小的數字有3 個；7到6的左循環區間比6小的數字有1個（如上面圖下半部所示）；6到5的左循環區間比5小的右3個數字（如上圖上半部分所示）；……；3到2的左循環區間里比2小的數字有1個。所以得到遞減中介數10031316（此中結束加上100的遞減進制數131得新中介數10031447）

還原方法：循環左移的還原方法很自然。首先畫9個空格。當拿到新的中介數后，從中介數的最右邊向左邊開始計數逐個計數。計數的方法是，對于中介數最右邊的數x9，從空格的最右端起數x9個空格，在第x9+1個空格上填上9。然后對于中介數的每一位xi，沿著左循環的方向數xi個未占用空格，在第xi+1個空格里填上i，即可完成還原。我給出了將中介數10031447還原的步驟，其中底紋代表為了定位下一個數字而數過的空格。紅色代表被填充的空格。最終得到結果592138647。

新中介數當前位	新排列數	備注
初始		在還原前，畫9個空格
7	9	從右向左數7個空格，第8個空格提填“9”
4	9       8	從9開始左循環數4個空格，第5個空格提填“8”
4	9       8     7	從8開始左循環數4個空格，第5個空格提填“7”
1	9       8 6   79	從7開始左循環數1個空格，第2個空格提填“6”
3	5 9       8 6   79	從6開始左循環數3個空格，第4個空格提填“5”
0	5 9       8 6 4 77	從5開始左循環數0個空格，第1個空格提填“4”
0	5 9     3 8 6 4 77	從4開始左循環數0個空格，第1個空格提填“3”
1	5 9 2   3 8 6 4 77	從3開始左循環數1個空格，第2個空格提填“2”
最后補位	5 9 2 1 3 8 6 4 7	余下的空格填“1”

 

與遞減進位排列生成算法一樣，循環左移排列生成算法也用到了遞減進位排列生成算法的加法運算函數。主要代碼如下：

/*

函數名稱：Permutation

函數功能：循環左移排列生成算法：輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個全排列的值，p[i]=i!

    p[0] = 1;

    for (int i=1; i<n; i++)

    {

        p[i] = (i + 1) * p[i-1];

    }

 

    int *b = new int[n];//用來存儲新的全排列

    int *yShe = new int[n-1]; //將原中介數加上序號i的遞減進位制數得到新的映射

    int *diJ = new int[n-1];

    for (int i=0; i<n-1; i++)

    {

        diJ[i] = yShe[i] = 0;

    }

   

    diJ[n-2] = 1;

    for (int c=0; c<p[n-1]; c++)

    {

        DiJYingShe(yShe, diJ, n);  //每次遞增1

       

        for (int i=0; i<n; i++) //新的全排列空格初始化

            b[i] = 0;

       

        int num = n;

        int pos = n - 1;

        for (int j=n-2; j>=0; j--) //獲取前n-1個數字

        {

            int s = 0;

            int k = pos;

            while (k >= 0 && s < yShe[j])

            {

                if (b[k] == 0) //該處未填數字

                    s++;

                k--;

            }

           

            //跳過已填數字

            while (k >= 0 && b[k] != 0)

                k--;

            if (b[k] != 0)//如果到了最左側還沒有找到適合的位置，從最右側繼續分析

            {

                k = n - 1;

                while (k > pos && b[k] != 0)//跳過非空位:b[j] == 0表示j位置是空位

                    k--;

            }

           

            //如果到了最左側還沒有找到適合的位置，從最右側繼續累積s

            if (s < yShe[j])

            {

                k = n - 1;

                while (k >= 0 && s < yShe[j])

                {

                    if (b[k] == 0)

                        s++;

                    k--;

                }

                while (k >= 0 && b[k] != 0) //跳過已填數字

                    k--;

            }

            b[k] = num--;

            pos = k;

        }

       

        for (int i=0; i<n; i++)//填充最后一個數字1

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

        Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diJ;

    delete []yShe;

}  

 

最后介紹一種準有序全排列生成算法：顛倒的協詞典順序算法。

這是Donald E.Knuth在《計算機程序設計藝術（第4卷 第2冊）》上介紹的一種方法。

該算法的原理為：設P是1～n的一個全排列:p = p1p2...pn

1）從排列的左端開始，找出第一個比右邊數字小的數字的序號j，即j = min{i | pi < pi+1}，如果j == n-1，表示已經輸出了所有的全排列。

2）在pj的左邊的數字中，找出所有比pj小的數中最大的數字pk，即 k = max{i | pi > pj}（左邊的數從左至右是遞減的，因此k是所有小于pj的數字中序號最大者）

3）對換pj，pk

4）再將p1p2...pj-1倒轉得到新的排列

以n = 3為例，我們可以得到全排列123，213，132，312，231，321.

仔細觀察這些序列，如果我們從右到左地反射這些序列，就可以得到321，312，231，213，132，123。

它剛好是字典序全排列的顛倒。所以如果我們逆序地輸出序列，是可以得到一個有序全排列的。

代碼如下：

/*

函數名稱：Permutation

函數功能：顛倒的協詞典順序算法：逆序輸出n個數的所有全排列

輸入變量：int n：1，2，3，...，n共n個自然數

輸出變量：無

*/

void Permutation(unsigned int n)

{

    int *a = new int[n];//用來存儲n個自然數

    for (int i=0; i<n; i++) //存儲全排列的元素值，并計算全排列的數量

    {

        a[i] = i + 1;

    }

   

    int temp, left, right;

    while (1)

    {

        Print(a, n);

        for (right=1; right<n; right++)//找出第一個比右邊數字小的數字的序號right-1

        {

            if (a[right-1] < a[right])

                break;

        }

        if (right == n) //表示已經輸出所有全排列

            break;

        //找到右邊界左邊數組中比a[right]小的最大的元素，這個就是要取代a[right]的元素

        for (left=0; a[left] >= a[right]; left++)

            ;

        temp = a[left]; a[left] = a[right]; a[right] = temp; //交換a[right]和a[left]

       

        left = 0;

        right--; //右邊界減1，保證此時左右邊界之間的元素是一個遞減排列

        while (left < right)//逆置左右邊界之間的元素，使其按增序排列

        {

            temp = a[left]; a[left] = a[right]; a[right] = temp;

            left++;

            right--;

        }

    }

   

    delete []a;

}

 

到這里我就把我目前所知的幾種非有序全排列算法都介紹完了，以下是上述七種方法的測試結果：（為了方便測試，我只要求輸出最后一個全排列）

當n = 10 時，普通遞歸算法用時0秒；全排列循環移位法用時0秒；排列鄰位對換法用時0秒；遞增進位排列生成算法用時3秒；遞減進位排列生成算法用時3秒；循環左移排列生成算法用時4秒；顛倒的協詞典順序算法用時0秒。

當n = 11 時，普通遞歸算法用時2秒；全排列循環移位法用時5秒；排列鄰位對換法用時2秒；遞增進位排列生成算法用時42秒；遞減進位排列生成算法用時39秒；循環左移排列生成算法用時54秒；顛倒的協詞典順序算法用時2秒。

當n = 12時，普通遞歸算法用時29秒；排列鄰位對換法用時25秒；顛倒的協詞典順序算法用時23秒。

全排列的應用非常廣泛，我們在很多地方都會遇到它，下次我將總結一下“列車出棧系列問題”，在該問題中，我們可以看到全排列的身影。

 

參考文獻：

1.《組合數學——排列數生成算法詳解》speedfirst 的Blog

http://www.newsmth.net/pc/pcdoc.php?userid=speedfirst&pid=0&tag=0&order=&tid=18452

2.《全排列的生成算法》 visame的專欄

http://blog.csdn.net/visame/archive/2008/05/18/2455396.aspx

 

附錄：

《康托展開》：http://blog.csdn.net/goal00001111/archive/2008/11/18/3326662.aspx

《遞增進位制和遞減進位制數》：

http://blog.csdn.net/goal00001111/archive/2008/11/18/3326765.aspx

《有序全排列生成算法集錦》

http://blog.csdn.net/goal00001111/archive/2008/11/18/3326642.aspx

《非有序全排列生成算法集錦》

http://blog.csdn.net/goal00001111/archive/2009/01/20/3839683.aspx