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 10Sample Output
1 1 1 2 2 2 1 2 3 1题意：给定一个集合{1，2，3，4….n}，求它内部的不同元素的字典序下的第m个字典序。 思路： 找规律吧 例：n=3，m=10时，有 {1} {1, 2} {1, 2, 3} {1, 3} {1, 3, 2} {2} {2, 1} {2, 1, 3} {2, 3} {2, 3, 1} {3} {3, 1} {3, 1, 2} {3, 2} {3, 2, 1}
n表示有多少组，g(n)表示每一组的个数，f(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 <algorithm> #include <cstdio> #include <cstring> #include <iostream> #include <vector> using namespace std; int main() { int n, a[25]; long long int m, c[21]; memset(c, 0, sizeof(c)); for (int i = 1; i <= 25; i++) c[i] = (i - 1) * c[i - 1] + 1; // c[25]保存当n=i时，每一组的个数 while (cin >> n >> m) { for (int i = 1; i <= n; i++) a[i] = i; while (n > 0 && m > 0) { int temp = (m - 1) / c[n] + 1; // 第几组=输出的数字 if (temp > 0) { printf("%d", a[temp]); for (int i = temp; i <= n; i++) { ///删掉这个数字 a[i] = a[i + 1]; } m -= ((temp - 1) * c[n] + 1); //再该组的第几项 printf(m == 0 ? "\n" : " "); } n--; } } return 0; }转载于:https://www.cnblogs.com/ruoh3kou/p/9893460.html
