c++ - 位产生的功率集

我有这段代码可生成大小为4的数组的幂集(数字仅是示例，可写的组合较少...)。

#define ARRAY_SIZE 4


unsigned int i, j, bits, i_max = 1U << ARRAY_SIZE;
int array[ARRAY_SIZE];

for (i = 0; i < i_max ; ++i) {
    for (bits = i, j = 0; bits; bits >>= 1, ++j) {
        if (bits & 1)
            printf("%d", array[j]);
    }
}

输出:

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
{4}
{1, 4}
{2, 4}
{1, 2, 4}
{3, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

我需要该输出是这样的:

{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

因此，必须像这样订购。在该算法结束后，我无法再进行排序，因此必须在每次迭代中使用每个组合，因此它必须生成已经排序的组合。有人可以帮我吗？我想我正在考虑一切...

编辑:最终输出应该没有空集，但它不是优先级。

最佳答案

这是一个版本，可以通过位旋转来解决。它使用著名的Hackers' Delight snoob() 函数的修改版本，该函数使用相同的一位数生成下一个更大的子集。请参阅Chess Programming Wiki(许多此类位纠缠例程的来源)。

#include <cstdint>
#include <iostream>

using U64 = uint64_t;

// print bit indices of x
void setPrint(U64 x)
{
    std::cout << "{ ";
    for(auto i = 1; x; x >>= 1, ++i)
        if (x & 1) std::cout << i << ", ";
    std::cout << "}\n";
}

// get next greater subset of set with
// Same Number Of One Bits
U64 snoob (U64 sub, U64 set) {
   U64 tmp = sub-1;
   U64 rip = set & (tmp + (sub & (0-sub)) - set);
   for(sub = (tmp & sub) ^ rip; sub &= sub-1; rip ^= tmp, set ^= tmp)
       tmp = set & (0-set);
   return rip;
}

void generatePowerSet(unsigned n)
{
    auto set = (1ULL << n) - 1;                 // n bits
    for (unsigned i = 0; i < n+1; ++i) {
        auto sub = (1ULL << i) - 1;             // i bits
        U64 x = sub; U64 y;
        do {
            setPrint(x);
            y = snoob(x, set);                  // get next subset
            x = y;
        } while ((y > sub));
    }
}

int main()
{
    generatePowerSet(4);
}

Live Example，按字典顺序输出(奖励功能)

{ }
{ 1, }
{ 2, }
{ 3, }
{ 4, }
{ 1, 2, }
{ 1, 3, }
{ 2, 3, }
{ 1, 4, }
{ 2, 4, }
{ 3, 4, }
{ 1, 2, 3, }
{ 1, 2, 4, }
{ 1, 3, 4, }
{ 2, 3, 4, }
{ 1, 2, 3, 4, }

关于c++ - 位产生的功率集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19299553/