问题描述
考虑总= { 1,2,…,n }。例如,A1 = { 1 },A3 = { 1,2,3 }。子集序列被定义为非空子集的数组。对词典编纂顺序中的所有子集进行排序。你的任务是找到第m个。
输入
输入包含几个测试用例。每个测试用例由两个数字n和m组成(0< n<= 20, 0< m<= a的子集序列的总数)。
输出
对于每个测试用例，您应该输出一行中的m-th子集序列。
样例输入
1
2 1
2 - 2
2 3
2 4
3 10
样例输出
1
1
1 2
2
2 1
1 2 3
问题分析：首先要找到对应n的总共排列方式。
n=1 :
1
n=2 :
1
1 2
2
2 1
n=3 :
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
可以分析得到新的可以平均分为n块，每块就是在第一位的基础上加上类似上一个数的排序方式和一个空集。这样就得到a[i]=i*(a[i-1] 1)表示总次数。
然而，排列的规律也可以找到。分成n块后，你就可以找到m所属的大区块，就可以先输出这个数，然后在查看这个数在小n区间内的余数（详细看代码）。再次使用类似的输出方式，直到结束为止。
你或许会疑问虽然找到小区间的分配方式相同，但是数字变了怎么变，可以用到Java集合初始化，然后标记位置，删除已经输出的元素。实行递归。有一点，如果余数刚好是1的就输出当前值然后停止。
代码如下：
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class 杭电2062 { public static void main(String []args){ Scanner sc=new Scanner(System.in); long a[]= new long [21];//a[n]表示个数；一定要用长整形，不然数字越界 a[1]=1; for(int i=2;i<21;i ) { a[i]=i*(a[i-1] 1); } while(sc.hasNext()) { long m=sc.nextLong(); long n=sc.nextLong(); if(m<=0||m>20||n<=0||n>a[(int) m]) {break;} List list=new ArrayList();//初始化。 for(int i=1;i<m 1;i ) { list.add(i); } out(m,n,a,list); System.out.println(); } } private static void out(long m, long n,long a[],List list) { //m第几个 a[m]总个数 n第几个 if(m==1) {System.out.print(list.get((int) (m-1)));}//不出意外输出到最后 else { long a1=a[(int) m]/m;//看每一小块有多少个数 long a2=(n-1)/a1 1;//当前要输出数（其实也是位置第一位对应的是他本身，后面就不一定）。这样可以避免刚好成倍数的数和前面分组不同 int a3=(int)a2; if(n
