非有序全排列生成算法

作者：goal00001111（高粱）

 

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

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

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

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

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

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

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

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

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

主要代碼如下：

/*

函數(shù)名稱：Permutation

函數(shù)功能：普通遞歸算法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(int n)

{

    int *a = new int[n];//用來存儲n個(gè)自然數(shù)

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

        a[i] = i + 1;

   

    Recursion(a, n, n-1); //調(diào)用遞歸函數(shù)     

    delete []a;

}

 

/*

函數(shù)名稱：Recursion

函數(shù)功能：遞歸輸出n個(gè)數(shù)的所有全排列

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

          int n：數(shù)組a[]的長度

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

輸出變量：無

*/

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

{

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

        Print(a, n);

    else

    {

        int temp;

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

        {

            temp = a[i];

            a[i] = a[k];

            a[k] = temp;

           

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

           

            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;

}

 

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

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

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

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

/*

函數(shù)名稱：Permutation

函數(shù)功能：全排列循環(huán)移位法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(int n)

{

    unsigned int *a = new unsigned int[n];//用來存儲n個(gè)自然數(shù)

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

    {

        a[i] = i + 1;

    }

   

    Recursion(a, n, 1);

   

    delete []a;

}

/*

函數(shù)名稱：Recursion

函數(shù)功能：循環(huán)左移遞歸輸出n個(gè)數(shù)的所有全排列

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

          int n：數(shù)組a[]的長度

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

輸出變量：無

 

*/

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++)//循環(huán)左移

        {

            temp = a[0];

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

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

            a[k-1] = temp;

            

            Recursion(a, n, k+1);

        }

    }

}

 

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

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

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

p1 p2…pn-1n

p1 p2…npn-1

np1 p2…pn-1

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

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

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

(1) n是第一個(gè)數(shù)，且其方向指向左側(cè)

(2) n是最后一個(gè)數(shù)，且其方向指向右側(cè)

于是，我們可按如下算法產(chǎn)生所有排列：

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

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

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

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

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

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

因?yàn)闆]有比4更大的數(shù)p，所以無需調(diào)整p的方向。最大數(shù)4到了最左邊后，由于其方向指向左側(cè)，所以4不能再移動。

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

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

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

此時(shí)最大數(shù)4到了最右邊，又因?yàn)槠浞较蛑赶蛴覀?cè)，所以4不能再移動；于是我們尋找最大的可移數(shù)3，將3與其箭頭所指的鄰數(shù)1互換位置，可以得到新排列：3 1 2 4；

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

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

如此循環(huán)，直到所有的數(shù)都不能移動，即可求出全部排列。最后得到的一個(gè)全排列為：2 1 3 4，此時(shí)2指向左側(cè)，1，3，4均指向右側(cè)。

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

/*

函數(shù)名稱：Permutation

函數(shù)功能：排列鄰位對換法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(int n)

{

    int  *a = new int[n];  //用來存儲n個(gè)自然數(shù)

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

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

    {

        a[i] = i + 1;

        p[i] = false; //開始均指向左側(cè)

    }

   

    do

    {

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

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

        {

            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在最左側(cè)，將其逐次與右側(cè)的元素交換，得到n - 1個(gè)新的排列

        {

            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;

}

 

/*

函數(shù)名稱：Move

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

          并將所得新排列中所有比m大的數(shù)p的方向調(diào)整

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

          bool p[]：存儲了n個(gè)元素的指向的數(shù)組：向左為false，向右為true

          int n：數(shù)組a[]的長度

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

*/

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]) || //指向右側(cè) 

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

        {

            max = a[i];

            pos = i;

        }

    }

   

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

        return false;

  

    //與其箭頭所指的鄰數(shù)互換位置

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

    {

        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 //指向左側(cè)

    {

        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大的數(shù)p的方向調(diào)整

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

    {

        if (a[i] > max)

            p[i] = !p[i];

    }

   

    return true;

}

 

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

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

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

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

 

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

主要代碼如下：

/*

函數(shù)名稱：Permutation

函數(shù)功能：遞增進(jìn)位排列生成算法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個(gè)全排列的值，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]; //將原中介數(shù)加上序號i的遞增進(jìn)位制數(shù)得到新的映射

    int *diZ = new int[n-1];  //用來存儲序號i的遞增進(jìn)位制數(shù)，設(shè)所有元素的初值為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個(gè)數(shù)字

        {

            int s = 0;

            int k = n - 1;

            while (s < yShe[j])

            {

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

                    s++;

                k--;

            }

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

                k--;

            b[k] = num--;

        }

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

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

        Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diZ;

    delete []yShe;

}

 

/*

函數(shù)名稱：DiZYingShe

函數(shù)功能：遞增進(jìn)位排列生成算法的加法運(yùn)算：yShe[] += dZJ[]

輸入變量：int yShe[]：原遞增進(jìn)制中介數(shù)；

          int diZ[]：遞增進(jìn)制數(shù)加數(shù)

          int len：最大自然數(shù)n的值

輸出變量：int yShe[]：新的增進(jìn)制中介數(shù)

*/

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--;

    }

}

 

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

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

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

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

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

 

主要代碼如下：

/*

函數(shù)名稱：Permutation

函數(shù)功能：遞減進(jìn)位排列生成算法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個(gè)全排列的值，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]; //將原中介數(shù)加上序號i的遞減進(jìn)位制數(shù)得到新的映射

    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個(gè)數(shù)字

        {

            int s = 0;

            int k = n - 1;

            while (s < yShe[j])

            {

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

                    s++;

                k--;

            }

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

                k--;

            b[k] = num--;

        }

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

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

    Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diJ;

    delete []yShe;

}

 

/*

函數(shù)名稱：DiJYingShe

函數(shù)功能：遞減進(jìn)位排列生成算法的加法運(yùn)算：yShe[] += dZJ[]

輸入變量：int yShe[]：原遞減進(jìn)制中介數(shù)；

          int diJ[]：遞減進(jìn)制數(shù)加數(shù)

          int n：最大自然數(shù)n的值

輸出變量：int yShe[]：新的遞減進(jìn)制中介數(shù)

*/

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--;

    }

}

 

循環(huán)左移排列生成算法

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

圖中展示了839647521種以開始數(shù)字為6，

結(jié)束數(shù)字為5和開始數(shù)字為7，結(jié)束數(shù)字為6的

左循環(huán)搜索區(qū)間，注意開始和結(jié)束數(shù)字是不包括

在區(qū)間內(nèi)的。

具體到循環(huán)左移的排列生成法的映射方法，

就是要為每一個(gè)數(shù)字確定這樣一個(gè)區(qū)間。方法是

以從9到2的順序依次產(chǎn)生中介數(shù)中的數(shù)字，中介數(shù)

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

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

新中介數(shù)當(dāng)前位	新排列數(shù)	備注
初始		在還原前，畫9個(gè)空格
7	9	從右向左數(shù)7個(gè)空格，第8個(gè)空格提填“9”
4	9       8	從9開始左循環(huán)數(shù)4個(gè)空格，第5個(gè)空格提填“8”
4	9       8     7	從8開始左循環(huán)數(shù)4個(gè)空格，第5個(gè)空格提填“7”
1	9       8 6   79	從7開始左循環(huán)數(shù)1個(gè)空格，第2個(gè)空格提填“6”
3	5 9       8 6   79	從6開始左循環(huán)數(shù)3個(gè)空格，第4個(gè)空格提填“5”
0	5 9       8 6 4 77	從5開始左循環(huán)數(shù)0個(gè)空格，第1個(gè)空格提填“4”
0	5 9     3 8 6 4 77	從4開始左循環(huán)數(shù)0個(gè)空格，第1個(gè)空格提填“3”
1	5 9 2   3 8 6 4 77	從3開始左循環(huán)數(shù)1個(gè)空格，第2個(gè)空格提填“2”
最后補(bǔ)位	5 9 2 1 3 8 6 4 7	余下的空格填“1”

 

與遞減進(jìn)位排列生成算法一樣，循環(huán)左移排列生成算法也用到了遞減進(jìn)位排列生成算法的加法運(yùn)算函數(shù)。主要代碼如下：

/*

函數(shù)名稱：Permutation

函數(shù)功能：循環(huán)左移排列生成算法：輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(unsigned int n)

{

    unsigned int *p = new unsigned int[n];//用來存儲各個(gè)全排列的值，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]; //將原中介數(shù)加上序號i的遞減進(jìn)位制數(shù)得到新的映射

    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個(gè)數(shù)字

        {

            int s = 0;

            int k = pos;

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

            {

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

                    s++;

                k--;

            }

           

            //跳過已填數(shù)字

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

                k--;

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

            {

                k = n - 1;

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

                    k--;

            }

           

            //如果到了最左側(cè)還沒有找到適合的位置，從最右側(cè)繼續(xù)累積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) //跳過已填數(shù)字

                    k--;

            }

            b[k] = num--;

            pos = k;

        }

       

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

        {

            if (b[i] == 0)

            {

                b[i] = 1;

                break;

            }

        }

       

        Print(b, n);

    }

   

    delete []b;

    delete []p;

    delete []diJ;

    delete []yShe;

}  

 

最后介紹一種準(zhǔn)有序全排列生成算法：顛倒的協(xié)詞典順序算法。

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

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

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

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

3）對換pj，pk

4）再將p1p2...pj-1倒轉(zhuǎn)得到新的排列

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

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

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

代碼如下：

/*

函數(shù)名稱：Permutation

函數(shù)功能：顛倒的協(xié)詞典順序算法：逆序輸出n個(gè)數(shù)的所有全排列

輸入變量：int n：1，2，3，...，n共n個(gè)自然數(shù)

輸出變量：無

*/

void Permutation(unsigned int n)

{

    int *a = new int[n];//用來存儲n個(gè)自然數(shù)

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

    {

        a[i] = i + 1;

    }

   

    int temp, left, right;

    while (1)

    {

        Print(a, n);

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

        {

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

                break;

        }

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

            break;

        //找到右邊界左邊數(shù)組中比a[right]小的最大的元素，這個(gè)就是要取代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，保證此時(shí)左右邊界之間的元素是一個(gè)遞減排列

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

        {

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

            left++;

            right--;

        }

    }

   

    delete []a;

}

 

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

當(dāng)n = 10 時(shí)，普通遞歸算法用時(shí)0秒；全排列循環(huán)移位法用時(shí)0秒；排列鄰位對換法用時(shí)0秒；遞增進(jìn)位排列生成算法用時(shí)3秒；遞減進(jìn)位排列生成算法用時(shí)3秒；循環(huán)左移排列生成算法用時(shí)4秒；顛倒的協(xié)詞典順序算法用時(shí)0秒。

當(dāng)n = 11 時(shí)，普通遞歸算法用時(shí)2秒；全排列循環(huán)移位法用時(shí)5秒；排列鄰位對換法用時(shí)2秒；遞增進(jìn)位排列生成算法用時(shí)42秒；遞減進(jìn)位排列生成算法用時(shí)39秒；循環(huán)左移排列生成算法用時(shí)54秒；顛倒的協(xié)詞典順序算法用時(shí)2秒。

當(dāng)n = 12時(shí)，普通遞歸算法用時(shí)29秒；排列鄰位對換法用時(shí)25秒；顛倒的協(xié)詞典順序算法用時(shí)23秒。

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

 

參考文獻(xiàn)：

1.《組合數(shù)學(xué)——排列數(shù)生成算法詳解》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

《遞增進(jìn)位制和遞減進(jìn)位制數(shù)》：

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