Subset sequence

Subset sequenceConsidertheaggregateAn={1,2,…,n}.Forexample,A1={1},A3={1,2,3}.Asubsetsequenceisdefinedasaarrayofanon-emptysubset.SortallthesubsetsequeceofAninlexicographyorder.Your…

大家好,欢迎来到IT知识分享网。Subset

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

不难发现,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>
#include<stdlib.h>
#include<iostream>
using namespace std;
int main()
{
	int i,n;//元素个数;
	int t;//所求子集位于分组后的第几组;
	int s[25];//后面将子集按字典序分组后每组的初始首元素;
	__int64 m;//位于第几个子集;
	__int64 c[25]={0};//c[i]表示n=i时的分组每组中子集数;
	for(i=0;i<25;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<25;i++)
		{
			s[i]=i;//每循环一次就重新归位每组首元素;
		}
		while(n>0&&m>0)
		{
			t=m/c[n]+1;
			if(m%c[n]==0)
			t--;
			if(t>0)//得到第m个子集在分组后的第t组
			{
				printf("%d",s[t]);
				for(i=t;i<=n;i++)
				{
					s[i]=s[i+1];//在第n组中,第2个元素在第n个时变为它的下一个数
				}
				m=m-((t-1)*c[n]+1);//去掉前面的小于t开头的组合,且将去掉一个仅有t的集合
				printf(m==0?"\n":" ");
			}
			n--;//n依次递减,直到执行上面的if代码或退出
		}
	}

}

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/12469.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信