由比特生成的功率集

Question

我有这个代码生成一个大小为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}

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

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

Answer 1

这是一个版本,可以追溯到金属的位置.它使用了着名的Hackers'Delightsnoob()函数的修改版本,该函数生成具有相同数量的一位的下一个更大的子集.请参阅国际象棋编程维基(许多此类比特小程序的来源).

#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);    
}

以字典顺序输出的实时示例(奖励功能)

{ }
{ 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, }