排列——逆康托展开

本文主要是介绍排列——逆康托展开，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

1,2,3,…n是自然数1到n的最小的排列，易知，第二小的排列是：1,2,3….n，n-1。现在给你2个值n和m，请找到1到n个数的第m小的排列。

Input

输入包括多组样例，对于每组样例包括两个整数n和m（1<=n<=1000,1<=m<=10000000)，分别如题目所述

Output

输出第m小的排列的后各个数字，中间用空格分开，每一个样例占一行

Sample Input

6 4
11 8
Sample Output

1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10
有关逆康托展开我就不赘述了，博客很多。。。这题是我们学校的提，要加1的特判，因为有一个数据错的
、

#include<stdio.h>
#include<string.h>
int jc[2000];
void init()
{jc[1]=1;jc[0]=1;for(int i=2;i<=13;i++){jc[i]=jc[i-1]*i;}
}
int ans[2000],vis[1005];
int main()
{init();int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==1){printf("1\n");continue;}memset(vis,0,sizeof(vis));memset(ans,0,sizeof(ans));int pos;m--;for(int i=1;i<=13;i++){if(jc[i]>m){pos=i;break;}}for(int i=1;i<=pos;i++){int ct=m/jc[pos-i];m=m-ct*jc[pos-i];int j;for(j=1;j<=n;j++){if(!vis[j]){if(ct==0)break;ct--;}}ans[i]=j;vis[j]=1;}for(int i=1;i<=n-pos;i++){printf("%d ",i);}for(int i=1;i<=pos;i++){printf("%d ",ans[i]+n-pos);}printf("\n");}return 0;
}

这篇关于排列——逆康托展开的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---