推出n=1到4时，An排列的种类数分别为
1 4 15 64
可得
(1+1)*2=4
(4+1)*3=15
(15+1)*4=64
...
故用一数列r[n]记录An的种类总数
当n=3时，列举出以下15种从大到小的排列
1
1 2
1 2 3
1 3
1 3 2
2
2 1
2 1 3
2 3
2 3 1
3
3 1
3 1 2
3 2
3 2 1
可得开头为1，2，3时分别由5种排列，并且这5种内都有一种是这个数自身
可得r[n]/n-1=r[n-1]，又得出上面的递推公式
所以定义一个数组rd[n]=r[n]/n
rd[n]则表示开头相同时的种类数
取上面列举的排列第2到第5项
去掉第一个1后，得到
2
2 3
3
3 2
即用2和3两个数进行同样的排列
故得出解题步骤：
再定义一个新数列dat，存放1到n的数字
每次用(m-1)/rd[n]+1得出第一个数现在在dat数列中的位置，输出后取出，该位置其后的所有数字前移一位
然后m需要移动至下一层的相对位置
(p-1)*rd[n]减去前面p-1块，再把当前块的唯一一个只有一个数字组成的序列去掉
所以m-=(p-1)*rd[n]+1
因为输出了一个，所以n-=1
一直循环下去，直到m和n其一为0，结束循环
1 /* 2 Written By. StelaYuri 3 */ 4 #include<stdio.h> 5 int main(){ 6 int i,n,p,dat[25]; 7 long long m,r[25],rd[25]; 8 r[0]=r[1]=rd[1]=1; 9 for(i=2;i<=20;i++){ 10 r[i]=(r[i-1]+1)*i; 11 rd[i]=r[i]/i; 12 } 13 while(scanf("%d%lld",&n,&m)!=EOF){ 14 for(i=1;i<21;i++) 15 dat[i]=i; 16 while(n&&m){ 17 p=(m-1)/rd[n]+1; 18 printf("%d",dat[p]); 19 for(i=p;i<=n;i++) 20 dat[i]=dat[i+1]; 21 m-=(p-1)*rd[n]+1; 22 putchar(m>0?‘ ‘:‘\n‘); 23 n--; 24 } 25 } 26 return 0; 27 }
ZJNU 1133 - Subset sequence——中级
原文：https://www.cnblogs.com/stelayuri/p/12213383.html