背景：全排列学习。
学习：1.我的方法是模拟康托展开式的逆用，求n个递增数的第m个排列。
康托展开式：对于一个n个数的排列，看它是所有全排列中第几个最小的数。如：五个数的自然数排列：{5，2,4,1,3}。对于5，有四个数比他小，则有4*4！个排列比他小，对于2，有一个数比他小，则有1*3!个排列比他小，对于4有两个数比他小（虽然2也比他小，但2前面已经用过了只看4后面比他小的数）则有2*2！个排列比他小..........可得康托展开：4*4！+3*1！+2*2！+1*0！+0*0！==104（注意：0！==1！/1==1）。
康托展开的逆用：对于给定的自然数排列n，求其第m个小的排列。如：对于五个自然数的排列{1,2,3,4,5}，求其第104个小的排列。首先104-1=103（减一的原因，对于第一个排列只需要o个数比他小）,103/4!得4余7，有4个数比他小的是五，故第一个数应该是5。7/3！得1余1，有1个数比他小的是2，故第二位是2.......可得：{5,2,4,1,3}。
我的代码：（注意：由于题中告诉m小于4000,7！=，故对于n>8时只需对最后八位数排位，开始没有发现这个阶乘很快会超出数据范围）（代码第二次看，都觉得太混乱，具有较大的代码低效，不具有清晰名了的特点，原因是没用充分想好方法就写，边写边改逻辑自然乱了）
<span style="font-size:18px;">#include<stdio.h>
int a[10001],b[10001],cc[10],xx[10];
int main(void)
{
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==1)
{
printf("%d\n",n);
}
else
{
if(n<=8)
{
for(int k=0;k<=n-1;k++)
{
a[k]=k+1;
}
int nj=1;/*存放n-1的阶乘*/
for(int i=--n;i>0;--i)
{
nj=nj*i;
}
--m;
int c,bl=0;/*c存放除数,bl是b的下标*/
for(int j=n;j>0;--j)
{
c=m/nj;
m=m%nj;
nj=nj/j;
b[bl]=a[c];
++bl;
for(int w=c;w<=n;w++)
{
a[w]=a[w+1];
}
}
b[bl]=a[0];
for(int e=0;e<n;++e)
{
printf("%d ",b[e]);
}
printf("%d\n",b[n]);
}
else
{
for(int k=0;k<=n-1;k++)
{
a[k]=k+1;
b[k]=k+1;
}
int k=n-7,mm=n;
for(int i=0;i<=7;i++)
{
cc[i]=k;
k++;
}
n=8;
int nj=1;/*存放n-1的阶乘*/
for(int i=--n;i>0;--i)
{
nj=nj*i;
}
--m;
int c,bl=0;/*c存放除数,bl是b的下标*/
for(int j=n;j>0;--j)
{
c=m/nj;
m=m%nj;
nj=nj/j;
xx[bl]=cc[c];
++bl;
for(int w=c;w<=n;w++)
{
cc[w]=cc[w+1];
}
}
xx[bl]=cc[0];
for(int i=mm-1,u=7;i>=mm-8;i--)
{
b[i]=xx[u];
--u;
}
for(int e=0;e<mm-1;++e)
{
printf("%d ",b[e]);
}
printf("%d\n",b[mm-1]);
}
}
}
return 0;
} </span>
百度逆展开代码：（看不懂）
<span style="font-size:18px;">intfac[]={1,1,2,6,24,120,720,5040,40320,362880};<span style="color:#FF0000;">/*直接建立阶乘表，比算方便*/</span>
int[]uncantor(int x,int k){
int res[]=new int[9];
inti,j,l,t;
bool eanh[]=new boolean[12];
for(i=1;i<=k;i++){
t=x/fac[k-i];
x-=t*fac[k-i];
for(j=1,l=0;l<=t;j++)
if(!h[j])l++;
j--;
h[j]=true;
res[i-1]=j;
}
return res;/*代码看不懂*/
}</span>
百度展开代码：（看懂）
<span style="font-size:18px;">long cantor(int s[],int n)<span style="color:#FF6666;">/*s表示欲求其为第小的排列，n为其中元素个数*/</span>
{
long int i,j,temp,num;
num=0;
for(i=0;i<n;i++)<span style="color:#FF6666;">/*对s中每一个数进行助理*/</span>
{
temp=0;
for(intj=i+1;j<n;j++)
{
if(s[j]<s[i])temp++;//判断几个数小于它
}
num+=fac[n-i-1]*temp;//(或num=num+fac[n-i-1]*temp;)
}
return (num+1);<span style="color:#FF6666;">/*因为最小排列，计算后num为0，故应该加1*/</span>
}</span>
但是：网上其他人大多用的stll里的next_permutation直接求下一个排列，求m-1次即可求得，第m小的排列。其原理：
设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}
2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}
3）对换pj，pk
4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。