首页 > 学院 > 开发设计 > 正文

Subset sequence

2019-11-08 01:36:11
字体:
来源:转载
供稿:网友
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. InputThe 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 ).OutputFor each test case, you should output the m-th subset sequence of An in one line.Sample Input
1 12 12 22 32 43 10Sample Output111 222 12 3 1我的思路 : 看了标准代码懵逼好久最终搞定。

按照数字大小顺序排序,

可以发现,输出的序列第一个是m除以n个数的排序数,比如2有2种组合,3每次有5种组合,如果组合数以数组a(n)表示,则有a(n)=(n-1)*a(n-1)+1的规律

剩下的依序输出,比如输入的n和m是3 10,则第一个输出的应当是10/5,考虑到3有5种组合,但是第五种是以1开头的最后一种序列,所以,m=10时,其实是2开头的最后一种序列。若是m=11,虽然m/5=2,但是已经是3开头的序列了,所以,计算第一个输出的数时,应该是t=m/n组合数+m%n组合数?1:0;意思是如果求余不为0,加一,这样就符合实际情况。以此类推,每当输出一个t,应当将t从常数数组内去除,也就是将t之后的数全部提前一位。

以下是我的代码:#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<iomanip>#include<string.h>using namespace std;int main( ){   int a[21] = {0}, i;   long long p[21] = {0}, n, m, t;   while (cin >> n >> m)   {        for (i = 0; i < 21; i++)        a[i] = i;        p[1] = 1;        for (i = 2; i < 21; i++)        p[i] = p[i-1] * (i - 1) + 1; //计算出每个数字有几种排列,如N=1时,数字1开头有1种排列;        //N=2时,数字1开头有2种排列;N=3时, 有5种排列。         while (n-- && m)       {           t = m / p[n+1] + (m % p[n+1] ? 1 : 0); //计算出该m是在哪一组           cout << a[t];           for (i = t; i <= n; i++)            a[i] = a[i+1];//删去已经排列那个数字           m = m - ((t - 1) * p[n + 1] + 1); // 去掉前面的小于t开头的组合,且将去掉一个仅有t的集合            if (m==0)            cout << "/n";           else cout << " ";       }   }    return 0;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表