goal00001111

非有序全排列生成算法

作者：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