POJ 1833排列解题报告

时间：2010-03-17 来源：MC_ACM

题目描述：

大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。

任务描述：
给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

Input

第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。

Output

对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。

Sample Input

3 1

2 3 1

3 1

3 2 1

10 2

1 2 3 4 5 6 7 8 9 10

Sample Output

3 1 2

1 2 3

1 2 3 4 5 6 7 9 8 10

解题思路

问题关键在于：给出一个排列a1a2a3…an后，如何求出下一个刚好比它大的排列？举个例子，1 5 3 2 4的下一个排列就是1 5 3 4 2，1 5 4 3 2的下一个排列就是 2 1 3 4 5。方法：从排列的倒数第二个数向前查找满足ai<ai+1的第一个数ai，即查找第一个左边小于右边的相邻的两个数。从ai+1…an中查找最小的比ai大的数aj，即刚好比ai大的数。将ai与aj进行交换，然后对ai+1…an按从小到大进行排序。得到的就是所要求的下一个排列。求下k个排列时，重复执行上面过程k次即可。

如求1 5 4 3 2的下一个排列，查找ai<ai+1的数得到a0(即1<5)，查找比刚好比a0大的数得到a4(即是2)，将a0与a4进行交换，并对a1…a4进行排序，得到下一个排列为2 1 3 4 5。

注意

1、考虑最大的排列的下一个排列是最小的排列，如5 4 3 2 1的下一个排列是1 2 3 4 5;

2、考虑效率，输入输出用scanf和printf，用cin和cout会超时。

代码

#include<algorithm>
using namespace std;
int cmp ( const void *a , const void *b )
{
    return *(int *)a - *(int *)b;
}
void getNext(int a[],int n)
{
    int i,j;
    if(n==1)
        return ;
    for(i=n-2;i>=0;--i)
    {
        if(a[i]<a[i+1])
            break;
    }
    if(i<0)
    {
        for(j=0;j<n;++j)
            a[j]=j+1;
        return;
    }
    int flag=i+1;
    for(j=i+2;j<n;++j)
    {
        if(a[j]<a[flag] && a[j]>a[i])
            flag=j;
    }
    int temp;
    temp=a[i];
    a[i]=a[flag];
    a[flag]=temp;
    qsort(a+i+1,n-1-i,sizeof(a[0]),cmp);
}
int main()
{
    int m,n,k;
    int a[1025];
    int i,j;
    scanf("%d",&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d",&n,&k);
        for(j=0;j<n;++j)
            scanf("%d",&a[j]);
        for(j=0;j<k;++j)
            getNext(a,n);
        for(j=0;j<n-1;++j)
            printf("%d ",a[j]);
        printf("%d\n",a[j]);

    }
    return 0;
}

POJ 1833排列 解题报告

POJ 1833排列解题报告