运用C语言的程序代码实现这个子集合的序列的问题，具体代码的编写方式是什么样的

Question

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.

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

Output
For each test case, you should output the m-th subset sequence of An in one line.

Sample Input
1 1
2 1
2 2
2 3
2 4
3 10

Sample Output
1
1
1 2
2
2 1
2 3 1

Answer 1

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include

#define MAX 20

int results[MAX];
int step;
int numcomb;

void output()
{
int i;
for (i = 0; i < numcomb; i++)
{
printf("%3d", results[i]);
}
printf("\n");
}

void work(int lowerlimit, int upperlimit, int num)
{
int i;
for (i = lowerlimit; i <= upperlimit - num; i++)
{
results[step++] = i;
if (num > 1)
work(i + 1, upperlimit, num - 1);
if (step >= numcomb)
{
output();
}
step--;
}
}

void comb(int n, int m)
{
step = 0;
numcomb = m;
work(0, n, numcomb);
}

void subset(int n)
{
int i;
for (i = 1; i <= n; i++)
{
comb(n, i);
}
}

int main(void)
{
int n;
printf("Please input a integer between 1 and %d: ", MAX);
scanf("%d", &n);
if (n <= 0 || n > MAX)
{
printf("Input error.\n");
return 1;
}
subset(n);
return 0;
}#include

#define MAX_N 5

int g_arr[MAX_N] = {0};
__int64 g_cnt = 0;

void Recur(int* arr, int arr_size, int req_cnt)
{
if (req_cnt > 0)
{
//数据没有选够，从剩下的数据中继续选

    //先选中最小的
    arr[0] = 1;
    //然后从剩下的arr_size - 1个数据中选req_cnt-1个数据
    Recur(arr+1, arr_size - 1, req_cnt-1);

    //回溯一下，跳过刚才选的那个最小数的情况
    arr[0] = 0;
    if ((arr_size - 1) >= (req_cnt ))
    {
        Recur(arr+1, arr_size - 1, req_cnt);
    }
}
else
{
    //找到一组完整数据
    ++g_cnt;

    //输出组合
    for(int i=0; i<MAX_N; i++)
    {
        if (g_arr[i] == 1)
        {
            printf("%d\t", i);
        }
    }
    printf("\n");
}

}

int main(int argc, char* argv[])
{
for(int i=1; i<=MAX_N; i++)
Recur(g_arr, MAX_N, i);

printf("total group = %I64u\n", g_cnt);
return 0;

}输出MAX_N=5的情况：
0
1
2
3
4
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
0 1 2 3
0 1 2 4
0 1 3 4
0 2 3 4
1 2 3 4
0 1 2 3 4
total group = 311
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include
#include
#include
int a[16]={0};
unsigned long c[16]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x0100,0x0200,0x0400,0x0800,0x1000,0x2000,0x4000,0x8000};
int b[16]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int huanerjinzhi(long d)
{
int i=0;
int count=1;int k=d;
int *p;p=a;
unsigned long *q;q=c;
memset(a,0,sizeof(int)*16);
if(!k) {return 0;}
else {while(k&=(k-1)){count++;}}
while(d)
{
if(d&(*q)){*p=1;d&=~(*q);p++;q++;}
else{*p=0;p++;q++;}
}
return count;
}
void jisuan(long n)
{
long i, j, t;
long r;
long k=(1<<n);
for(i=0;i<k;i++)
{
t=huanerjinzhi(i);
printf("{");
for(r=1,j=0;r<=t;j++)
if(a[j]==1){
if(r!=t)printf("%d,",b[j]);
else printf("%d",b[j]);r++;}
printf("}\n");
}
}
void main()
{
int n;
printf("input a number:\n");
scanf("%d", &n);
long lBegin = GetTickCount();
jisuan(n);
long lEnd = GetTickCount();
printf("%d\n",lEnd-lBegin);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
input a number:
5
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
{4}
{1,4}
{2,4}
{1,2,4}
{3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
{5}
{1,5}
{2,5}
{1,2,5}
{3,5}
{1,3,5}
{2,3,5}
{1,2,3,5}
{4,5}
{1,4,5}
{2,4,5}
{1,2,4,5}
{3,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
16
Press any key to continue

0 2008-03-21 08:43:05 只看TA 引用 举报 #5 得分 0

ryfdizuo
Bbs9
Blank Blank Blank Blank
C/C++ code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//顺序反的...
#include
#include

int zuoyi(int n)
{
int i = 1< return i-1;
}
int main()
{
int k[100];
int p = 0, q,i,j;
int n;
scanf("%d",&n);
p = zuoyi(n);
for ( i = 0; i {
j = i;
for ( q = 0; j > 0; q++ )
{
k[q] = j%2;
j = j/2;
}
printf(" { ");
while (q--)
{
if ( k[q] ) printf("%d ",q+1);
}

printf("}\n");
}
return 0;
}