2013
12-29

Subset sequence

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.

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 ).

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 ).

1 1
2 1
2 2
2 3
2 4
3 10

1
1
1 2
2
2 1
2 3 1

#include <iostream>
#include <cstring>
using namespace std;

int seq[25], idx;
long long kind[25];
int vis[25];

void deal(int N, long long M) {
bool finish = false;
while (!finish) {
for (int i = 1; i <= N; ++i) {
if (M == 1) {
seq[++idx] = i;
finish = true;
break;
} else if (M > (kind[N-1] + 1)) {
M -= kind[N-1] + 1;
} else {
seq[++idx] = i;
M -= 1;
N -= 1;
break;
}
}
}
}

int main() {
int N;
long long M;
kind[1] = 1;
for (int i = 2; i <= 20; ++i) {
kind[i] = i * (kind[i-1] + 1); // i个不同元素集合的非空字典序子集个数
}
while (cin >> N >> M) {
memset(vis, 0, sizeof (vis));
idx = -1;
deal(N, M);
int first = 1;
for (int i = 0; i <= idx; ++i) {
int x;
// seq记录的是一个伪序列，即确定一个数字后又将后面的序列重排
for (int j = 1; j <= N; ++j) {
if (!vis[j]) --seq[i];
if (!seq[i]) {
if (first) {
cout << j;
first = 0;
} else cout << " " << j;
vis[j] = 1;
break;
}
}
}
cout << endl;
}
return 0;
}

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

4. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}

5. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。