Subset sequence

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12987 Accepted Submission(s): 5523

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

Sample Output

解题思路：

不难发现，An可以按首数字分成n组，而每组里除了第一项，剩下的就是An-1的子集合了。

∴f(n) = n[f(n-1) + 1]

f(1) = 1

我们拿测试数据3 10来做个示范，解释一下怎么求解。

因为n=3，所以开始数组里1、2、3三个数。

我们知道，n=2时，有4种排列，所以上面n=3可以分成三组，每组5个(加上空集)。

因此第10个在第二组里。所以第一个是2，把2输出。原来的数组里删除2，变成1、3两个数。然后10 - (2 - 1) * 5 = 5，即它在第2组的第5个。

减去首个空集合，5 - 1 = 4 ≠ 0，表示2后面还有数字。

因为A1 = 1是，所以再第2组里又可以分成两组，每组2个(加上空集)。

所以，4在第2组，剩下的数组中，第二个元素是3，所以输出3。再把数组里的3删除，剩下1一个数。

然后4 - (2 - 1) * 2 = 2，既它是第2组的第2个。

减去首个空集，2 - 1 = 1 ≠ 0，表示2后面还有数字。

按上面的方法继续下去，直到n = 0 或后面为空集为止。

最后输出数组里的第1个元素，就得到2 3 1，就是解了。

从上面的计算可以看出来，本题目的关键是先求的An中每一组的个数g(n)

不难得出:g(n) = f(n) / n

∵f(n) = n[f(n-1) + 1]

∴g(n) = n[f(n-1) + 1] / n = f(n-1) + 1

∵f(n-1) = (n-1) * g(n-1)

∴g(n) = (n-1) * g(n-1) + 1

————————————————

代码：

#include <stdio.h>
int main()
{
    int i,n,t;//n：一共多少元素<=20。t：所求子集位于分组后的第几组
    __int64 m;//位于第几个子集
    __int64 c[21]={0};//后面将子集分组后平均每组个数，如:c[2]表示n=2时的分组每组中子集数
    int s[21];//后面将子集按字典序分组后每组的初始首元素,组数<=20
 
 
    for (i=1;i<21;i++)
        c[i]=c[i-1]*(i-1)+1;//推导出来的c[n]=(n-1)*c[n-1]+1
    while (scanf("%d%I64d",&n,&m)!=EOF)
    {
        for(i=0;i<21;i++)
            s[i]=i;//每循环一次就重新归位每组首元素
        while (n>0&&m>0)
        {
            t=m/c[n]+(m%c[n]>0?1:0);
            if(t>0)//得到第m个子集在分组后的第t组,若t>0
            {
                printf("%d",s[t]);
                for(i=t;i<=n;i++)
                    s[i]=s[i+1];//或s[i]+=1,我们发现:第n组中，第2个元素在第n个时变为它的下一个数
                m-=((t-1)*c[n]+1);//减去(t-1组总子集数+1）,m变为表示在剩余子集中位于第几个
                putchar(m==0?'\n':' ');
            }
            n--;//依次递减,直到执行上面的if代码或退出
        }
 
 
    }
    return 0;
}

hdu 2062 Subset sequence

Subset sequence