Power set generated by bits

Question

I have this code which generates power set of an array of size 4 (number is just example, less combinations to write...).

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

Output:

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

I need that output to be like this one:

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

So it has to be ordered like that. I can't do that ordering after that algorithm ends, I have to use every combination in every iteration, so It has to generate that combinations already ordered. Can someone help me out? I think I was thinking about everything...

EDIT: That final output should be without empty set, but it's not priority.

Answer 1

Here's a version that goes down to the metal with bit-twiddling. It uses a modified version of the famous Hackers' Delight snoob() function that generates the next greater subset with the Same Number Of One Bits. See the Chess Programming Wiki (a source of many such bit-twiddling routines).

#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 with output in lexicographic order (bonus feature)

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