所以如果我得到一个数组,例如
a = {1, 2, 3}
我们知道给定的子数组(包括非连续的)是(这代表幂集)
{1} {2} {3} {1,2,3} {1,2} {1,3} {2,3}
我也知道这些子集可以用二进制计数来表示
000 -> 111 (0 to 7), where each 1 bit means we 'use' this value from the array
e.g. 001 corresponds to the subset {3}
我知道这种方法可以以某种方式用于生成所有子集,但我不太确定如何在 C++ 中实现它
所以基本上我要问的是如何(如果可以)使用二进制计数来生成幂集?
也非常感谢任何其他生成幂集的方法!
最佳答案
对于包含 3 个集合元素的示例,您可以这样做:
for (s = 1; s <= 7; ++s)
{
// ...
}
这是一个演示程序:
#include <iostream>
int main()
{
const int num_elems = 3; // number of set elements
const int elems[num_elems] = { 1, 2, 3 }; // mapping of set element positions to values
for (int s = 1; s < (1 << num_elems); ++s) // iterate through all non-null sets
{
// print the set
std::cout << "{";
for (int e = 0; e < num_elems; ++e) // for each set element
{
if (s & (1 << e)) // test for membership of set
{
std::cout << " " << elems[e];
}
}
std::cout << " }" << std::endl;
}
return 0;
}
编译和测试:
$ g++ -Wall sets.cpp && ./a.out
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
请注意,让最低有效位对应于第一个集合元素是一种常见的约定。
另请注意,我们省略了空集 s = 0,因为您似乎不想包括它。
如果您需要使用大于 64 个元素的集合(即 uint64_t
),那么您将需要一个更好的方法 - 您可以扩展上述方法以使用多个整数元素,或使用 std::bitset
或 std::vector<bool>
,或使用类似@Yochai 的答案(使用 std::next_permutation
)。
关于c++ - 使用二进制计数对数组的所有子集进行计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25501051/