我正在尝试寻找幂集中的第n个集合。这里的n是指按照以下顺序生成幂集 -- 首先按大小，然后按字典序 -- ，因此，对于[a, b, c]的幂集中的集合索引为：
0 - []
1 - [a]
2 - [b]
3 - [c]
4 - [a, b]
5 - [a, c]
6 - [b, c]
7 - [a, b, c]
next_combination函数，如果有帮助的话，可以使用。它假设您可以将位掩码适配到某些整数类型中，鉴于64元素集合有264种可能性，这可能是一个不太合理的假设。[]，[a]，[ab]，[abc]，[ac]，[b]，[bc]，[c]。但我以前必须按“先按大小，然后按字典序”进行枚举。// Generate bitmaps representing all subsets of a set of k elements,
// in order first by (ascending) subset size, and then lexicographically.
// The elements correspond to the bits in increasing magnitude (so the
// first element in lexicographic order corresponds to the 2^0 bit.)
//
// This function generates and returns the next bit-pattern, in circular order
// (so that if the iteration is finished, it returns 0).
//
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
UnsignedInteger last_one = comb & -comb;
UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
else if (last_one > 1) return mask / (last_one / 2);
else return ~comb & 1;
}
第5行代码实现了位运算的替换操作，相当于使用（扩展）正则表达式查找字符串中最后一个01，将其翻转为10并将后面所有的1向右移动。
s/01(1*)(0*)$/10\2\1/
如果前一个操作失败，第6行代码执行以下操作：添加一个额外的1并将所有1向右移：
s/(1*)0(0*)/\21\1/
我不知道那个解释是帮助还是阻碍 :)
这是一个快速而简单的驱动程序（命令行参数是集合的大小，默认为5，最大值为无符号长整型的位数）：
#include <iostream>
template<typename UnsignedInteger>
std::ostream& show(std::ostream& out, UnsignedInteger comb) {
out << '[';
char a = 'a';
for (UnsignedInteger i = 1; comb; i *= 2, ++a) {
if (i & comb) {
out << a;
comb -= i;
}
}
return out << ']';
}
int main(int argc, char** argv) {
unsigned int n = 5;
if (argc > 1) n = atoi(argv[1]);
unsigned long mask = (1UL << n) - 1;
unsigned long comb = 0;
do {
show(std::cout, comb) << std::endl;
comb = next_combination(comb, mask);
} while (comb);
return 0;
}
很难想象这个函数对于一个超过64个元素的集合可能是有用的，鉴于枚举的大小，但它可能对于枚举一些有限的部分是有用的，例如所有三个元素的子集。在这种情况下，位运算技巧只有在修改适合单个字时才真正有用。幸运的是，这很容易测试；您只需要在位集中的最后一个单词上执行上述计算，直到测试last_zero为零为止。（在这种情况下，您不需要使用mask进行按位与操作，实际上您可能希望选择一种不同的指定集合大小的方式。）如果last_zero结果为零（这实际上非常少见），那么您需要以其他方式进行转换，但原则是相同的：找到在1之前的第一个0（注意0在一个字的结尾而1在下一个字的开头的情况）；将01更改为10，找出需要移动的1的数量，并将它们移到末尾。
考虑一个元素列表 L = [a, b, c]，L 的幂集由以下组成：
P(L) = {
[],
[a], [b], [c],
[a, b], [a, c], [b, c],
[a, b, c]
}
将每个位置视为一个位，您将具有以下映射：
id | positions - integer | desired set
0 | [0 0 0] - 0 | []
1 | [1 0 0] - 4 | [a]
2 | [0 1 0] - 2 | [b]
3 | [0 0 1] - 1 | [c]
4 | [1 1 0] - 6 | [a, b]
5 | [1 0 1] - 5 | [a, c]
6 | [0 1 1] - 3 | [b, c]
7 | [1 1 1] - 7 | [a, b, c]
id并不直接映射到整数。需要应用适当的映射，以便你有：id | positions - integer | mapped - integer
0 | [0 0 0] - 0 | [0 0 0] - 0
1 | [1 0 0] - 4 | [0 0 1] - 1
2 | [0 1 0] - 2 | [0 1 0] - 2
3 | [0 0 1] - 1 | [0 1 1] - 3
4 | [1 1 0] - 6 | [1 0 0] - 4
5 | [1 0 1] - 5 | [1 0 1] - 5
6 | [0 1 1] - 3 | [1 1 0] - 6
7 | [1 1 1] - 7 | [1 1 1] - 7
为了解决这个问题，我想到使用二叉树进行映射-- 我发布它是为了让其他人能够从中看到一个解决方案:
#
______________|_____________
a / \
_____|_____ _______|______
b / \ / \
__|__ __|__ __|__ __|__
c / \ / \ / \ / \
[ ] [c] [b] [b, c] [a] [a, c] [a, b] [a, b, c]
index: 0 3 2 6 1 5 4 7
#include <stdio.h>
int ch[88][88];
int choose(int n, int k) {
if (n<0||k<0||k>n) return 0;
if (!k||n==k) return 1;
if (ch[n][k]) return ch[n][k];
return ch[n][k] = choose(n-1,k-1) + choose(n-1,k);
}
int nthkset(int N, int n, int k) {
if (!n) return (1<<k)-1;
if (choose(N-1,k-1) > n) return 1 | (nthkset(N-1,n,k-1) << 1);
return nthkset(N-1,n-choose(N-1,k-1),k)<<1;
}
int nthset(int N, int n) {
for (int k = 0; k <= N; k++)
if (choose(N,k) > n) return nthkset(N,n,k);
else n -= choose(N,k);
return -1; // not enough subsets of [N].
}
int main() {
int N,n;
scanf("%i %i", &N, &n);
int a = nthset(N,n);
for (int i=0;i<N;i++) printf("%i", !!(a&1<<i));
printf("\n");
}