Subset sequence
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4123 Accepted Submission(s):
2019
Problem Description
Consider the aggregate An= { 1, 2, …, n }. For example,
A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty
subset. Sort all the subset sequece of An in lexicography order. Your task is to
find the m-th one.
A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty
subset. Sort all the subset sequece of An in lexicography order. Your task is to
find the m-th one.
Input
The input contains several test cases. Each test case
consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number
of the subset sequence of An ).
consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number
of the subset sequence of An ).
Output
For each test case, you should output the m-th subset
sequence of An in one line.
sequence of An in one line.
Sample Input
1 1
2 1
2 2
2 3
2 4
3 10
2 1
2 2
2 3
2 4
3 10
Sample Output
1
1
1 2
2
2 1
2 3 1
1
1 2
2
2 1
2 3 1
Author
LL
Source
Recommend
学习网址：http://blog.****.net/lianqi15571/article/details/8877014
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
long long c[]={};//c[n]表示长度为n，第一位固定，剩下数字排列形成数列的个数
//易知c[n]=(n-1)*c[n-1]+1
//含义：比如第一位是A1 剩下A2A3。。An 共n-1个数可以固定在第二位，再加上一个空集
bool s[];
int main(){
//freopen("D:\\INPUT.txt","r",stdin);
int n,i,j;
long long m;
for(i=;i<;i++){
c[i]=(i-)*c[i-]+;
//cout<<c[i]<<endl;
}
long long t,count;
while(scanf("%d %lld",&n,&m)!=EOF){
memset(s,false,sizeof(s));
j=n;
queue<int> q;
while(m){
count=;
t=m/c[j]-(m%c[j]==?:);
m-=t*c[j];
m--;//去掉一个空集!!
j--;
for(i=;i<=n;i++){
if(!s[i]){
count++;
if(count==t+){
break;
}
}
}
s[i]=true;
q.push(i);
}
printf("%d",q.front());
q.pop();
while(!q.empty()){
printf(" %d",q.front());
q.pop();
}
printf("\n");
}
return ;
}