使用二进制计数对数组的所有子集进行计数

Question

所以如果给我一个数组如

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 ++中实现

因此，基本上，我要问的是如何（如果可以的话）使用二进制计数来生成功率集？

任何其他用于生成功率集的方法也将不胜感激！

Answer 1

对于带有3个set元素的示例，您可以执行以下操作：

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 }

请注意，使最低有效位与第一个set元素相对应是一种常见的约定。

还要注意，由于您似乎不想包括该值，因此我们忽略了空集s = 0。

如果您需要使用大于64个元素的集合（即uint64_t），那么您将需要一个更好的方法-您可以扩展上述方法以使用多个整数元素，或者使用std::bitset或std::vector<bool>，或使用类似@Yochai的答案（使用std::next_permutation） 。