全排列生成

<< POJ 1094 - Sorting It All Out | 首页 |

日期：2010-10-01 | 分类：算法

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
 http://shilcare.blogbus.com/logs/76060678.html

全排列生成的办法很多，比如可以直接DFS遍历，像走迷宫一样，从起点开始，然后从这n个点选一

个走，并打上标记，然后走下一点，走下一点前，看看那个点是不是被标记了，没标记的再走。下一

点要是能走的都走过了，就退上一步换另一个点，走到不能走为止。

单纯的文字表达有点抽象，举个例子，123的全排列，生成流程：

第一个数选1

第二个数，1已选走，跳过

第二个数选2

第三个数，1已选走，跳过

第三个数，2已选走，跳过

第三个数选3 ->“123”

第三个数无可选数，返回到选第二个数

第二个数选3

第三个数，1已选走，跳过

第三个数选2 ->“132”

第三个数无可选数，返回到选第二个数

第二个数无可选数，返回到选第一个数

第一个数选2

第二个数选1

第三个数，1已选走，跳过

第三个数，2已选走，跳过

第三个数选3 ->“213”

……

第一个数选3

第二个数选1

第三个数，1已选走，跳过

第三个数选2 ->“312”

第三个数无可选数，返回到选第二个数

第二个数选2

第三个数选1 ->“321”

以上过程用于生成有序全排列，代码就不给出了。

如果不打算考虑次序，那么有更快的办法

上一个办法，主要慢在了标记，和循环判断是否有标记，为了省略标记，

我们直接规定第n个数直接取数组下标为n的元素，而数组中的内容通过交换得到各种排列

这个不是很好描述，直接给个代码看好了：

#include <stdio.h>

#define swap(a,b) a^=b^=a^=b

int dfs(int arr[], int len, int d)

{

    int l=len-d, i;

    if (l<=0)

    {

        for (i=-len; i<0; ++i)

        {

            printf("%d ", arr[i]);

        }

        puts("");

        return 1;

    }

    dfs(arr+1, len, d+1);

    for (i=1; i<l; ++i)

    {

        swap(arr[0], arr[i]);

        dfs(arr+1, len, d+1);

        swap(arr[0], arr[i]);

    }

    return 0;

}

int main()

{

    int arr[] = {1,2,3,4};

    dfs(arr,4,0);

    return 0;

}

还有一种生成的办法，是STL所使用的，直接根据前一个排列生成下一排列，

比如你传入一个数组{2,3,4,1}，它会算出{2,4,1,3}并返回

其计算方法如下：

1.从右边开始，找出第一组相邻的一对元素，满足右边的比左边要大的的组（如果没有，就是最后一个排列）

2.这对元素的左边那个记为A，然后从它右边找出比A大，并且是当中最小的一个元素B，A与B对调

3.对调后，原来A的位置的右边的所有元素形成一个递减数列，把那个数列逆序一下，完成。

以{2,3,4,1}为例，3就是元素A，4是元素B，AB对调后{2,4,3,1}，最后右边两个元素逆序，得到{2,4,1,3}

这个算法的优点显而易见，可以对任意当中的一个排列，求下一个，或者前一个排列，

而不需要多记录其它状态，使用起来相当方便。

最后要介绍的一种，也是生成难度较高的一种，根据排列本身的大小顺序，进行编号：

0 123

1 132

2 213

3 231

4 312

5 321

直接根据其编号，生成出相应的排列。

为了从编号直接得到排列，需要引入一种特殊的进制计算：

s = an * n! + a(n-1) * (n-1)! + .... + a2 * 2! + a1 * 1!

举个例子，我们需要四个元素的全排列中的第11小的排列，首先把11这个数按这个进制分解：

11 = 1 * 3! + 2 * 2! + 1 * 1! （一共三项，n个元素就应该有n-1项，不足的高位补0）

其系数单独列出得1 2 1，一共三个数，最后补一个0，得到1 2 1 0，然后和要排列的四个元素做如下处理：

1 2 1 0 1 2 3 4

↑取右边数组下标为1的元素 ==> 2

2 1 0 1 3 4

↑取右边数组下标为2的元素 ==> 4

1 0 1 3

↑取右边数组下标为1的元素 ==> 1

0 3

↑取右边数组下标为0的元素 ==> 3

按照取的次序，我们得到2 4 1 3这个排列，这个排列就是第11小的排列，不信你可以手工验算一下。

根据以上算法，可以得到编号转排列及排列转编号两段C++代码：

int f[20] = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800}; //按你需要把阶乘表填入

int PermutationToInt(int m[], int len)

{

    int n[20] = {0};

    int s=0;

    for (int t=0; t<len; ++t)

    {

        int nc=0;

        n[m[t]] = 1;

        for (int d=0; d<m[t]; ++d) nc += (n[d]>0);

        s += f[len-t-1]*(m[t]-nc);

    }

    return s;

}

void IntToPermutation(int num, int len, int m[])

{

    int n[20] = {0};

    for (int t=0; t<len; ++t)

    {

        int nc=0;

        while ( num>= f[len-t-1] )

        {

            ++nc; num -= f[len-t-1];

        }

        for (int d=0; d<=nc; ++d)nc += (n[d]>0);

        n[nc] = 1; m[t] = nc;

    }

}

参数说明：

len: 全排列元素个数

m: 全排列元素（输入/输出）

num: 编号/序号

第一个函数的返回值为编号

文章第二部分：老算法的改进

第一篇文章，附了一段生成全排列，但不保证次序从小到大的代码，现在，我们来改进这一段代码，

使得它能生成从小到大的排列，并且效率比原来的更高：

#include <stdio.h>

#define swap(a,b) a^=b^=a^=b

int dfs(int arr[], int len, int d)

{

    int l=len-d, i,j;

    if (l<=0)

    {

        for (i=-len; i<0; ++i)

        {

            printf("%d ", arr[i]);

        }

        puts("");

        return 1;

    }

    dfs(arr+1, len, d+1);

    for (i=1; i<l; ++i)

    {

        swap(arr[0], arr[i]);

        dfs(arr+1, len, d+1);

    }

    j = arr[0];

    for (i=1; i<l; ++i)

    {

        arr[i-1] = arr[i];

    }

    arr[l-1] = j;

    return 0;

}

int main()

{

    int arr[] = {1,2,3,4};

    dfs(arr,4,0);

    return 0;

}