关于排列(poj1833)问题

Description
题目描述：
大家知道，给出正整数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
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

#include<stdio.h>//头文件
int a[10][1024];//定义数列，存储初始数据，并推出下K个排列，更新数据存储
void A(int i,int p,int n)//定义一个简单的调换数据并排序的函数
{
    int j,k,l;//定义变量
    k=i;//储存初始i的值
    for(i=i+1;i<n;i++)//寻找刚好比a［p］［k］大一的数并调换位置
    {
        if (a[p][i]==a[p][k]+1)//符合条件，则
        {
            j=a[p][k];//调换位置
            a[p][k]=a[p][i];//调换位置
            a[p][i]=j;//调换位置
            break;//跳出此循环
        }
    }
    for (i=k+1;i<n;i++)//将后面的数据进行排序，选择排序
    {
        for(l=i+1;l<n;l++)//将后面的数据进行排序，选择排序
        {
            if (a[p][i]>a[p][l])//当前面的数据大于后边的则调换位置
            {
                j=a[p][l];//调换位置
                a[p][l]=a[p][i];//调换位置
                a[p][i]=j;//调换位置
            }
        }
    }
}
void B(int k,int n,int p)//定义一个递归函数，用来实现数据的循环，当数据是最后一个排列时，可以借此实现下一个排列从1，2，3……n开始
{
    int i,q,o,l;
    while (k--)//循环一次得到下一个排列，下k个排列循环k次
    {
        for (i=n-2;i>=0;i--)//从倒数第二个数开始检索
        {
            if (a[p][i]<a[p][i+1])//当相邻的两个数前者大于小于后者，则
            {
                A(i,p,n);//调用函数，即上方自定义函数，简单的调换数据并排序
                break;//跳出此循环
            }
        }
        if(i<0)//当排列中没有前者小于后者的两个相邻数据时
        {
            l=n-1;//用来表示数组中的最后一个数据的
            for(q=0;q<n/2;q++)//当出现这种情况时，肯定是由n到1依次排列，按题意需要调换对称位置的数据
            {
                o=a[p][q];//调换数据
                a[p][q]=a[p][l-q];//调换数据
                a[p][l-q]=o;//调换数据
            }
            B(k,n,p);//递归
        }
    }
}
int main()//主函数
{
    int b[10];//定义一个数组存储所有的n
    int i,n,m,k,p;//定义数据，变量
    scanf("%d",&m);//输入m，表示下面有m组数据
    for(p=0;p<m;p++)//输入m组数据并处理数据
    {
        scanf("%d%d",&n,&k);//输入每组数据的n与k
        for (i=0;i<n;i++)//循环n次存储1到n（无顺序）
        {
            scanf("%d",&a[p][i]);//输入1到n中的数据（每个数据存储一次），保存至数组a［p］中
        }
        b[p]=n;//存储每组数据的n到数组p中
        B(k,n,p);
    }
    for(p=0;p<m;p++)//循环m次，输出m组数据
    {
        for(i=0;i<b[p];i++)//每组数据输出前b［p］项
        {
            printf("%d ",a[p][i]);//输出每组数据，每组数据占一排
        }
        printf("\n");//换行
    }
    return 0;//返回0
}

P.S.2018.3.7 更新
此代码是刚开始接触编程时写的，很多东西那时候都一无所知，也不知道这种题需要在叫做 OJ 的东西上提交，所以就以为输出样例过了就算对了，现在有些尴尬，有大佬指出我的代码超时了，我也一直没有抽出时间回头改这个题，近期一直在折腾考研的事情，也没有时间去仔细改这个题，给大家推荐一个大佬的代码，见谅~~~键盘上的舞者’s blog

关于排列(poj1833)问题

全站热榜