Chinaunix首页 | 论坛 | 博客
  • 博客访问: 340201
  • 博文数量: 122
  • 博客积分: 5000
  • 博客等级: 大校
  • 技术积分: 1191
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-24 11:12
文章分类

全部博文(122)

文章存档

2010年(122)

我的朋友

分类: C/C++

2010-03-06 16:10:35

 

资源来源:http://blog.chinaunix.net/u3/105033/index.html

 

题目描述:

大家知道,给出正整数n,则1nn个数可以构成n!种排列,把这些排列按照从小到大的顺序(字典顺序)列出,如n=3时,列出1 2 31 3 22 1 32 3 13 1 23 2 1六个排列。

任务描述:
    给出某个排列,求出这个排列的下k个排列,如果遇到最后一个排列,则下1排列为第1个排列,即排列1 2 3…n
比如:n = 3k=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个正整数,是12 … n的一个排列。

Output

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

Sample Input

3

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 21 5 4 3 2的下一个排列就是 2 1 3 4 5。方法:从排列的倒数第二个数向前查找满足aii+1的第一个数ai,即查找第一个左边小于右边的相邻的两个数。从ai+1…an中查找最小的比ai大的数aj,即刚好比ai大的数。将aiaj进行交换,然后对ai+1…an按从小到大进行排序。得到的就是所要求的下一个排列。求下k个排列时,重复执行上面过程k次即可。

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

注意

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

    2、考虑效率,输入输出用scanfprintf,用cincout会超时。

代码


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


阅读(1982) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~