Power set of a given set

Question

Given a set I want to display all its subsets (its power set). I have found this code:

void printPowerSet(char *set, int set_size)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
      for(j = 0; j < set_size; j++)
       {

          if(counter & (1<<j))
            printf("%c", set[j]);
       }
       printf("\n");
    }
}

I can't understand why this part is used

 if(counter & (1<<j))

what is its meaning?

The time complexity for this algorithm is O(n2^n) is there any better method?

This translates to this: if `counter`, bitwise has bit nbr. `j` set to 1, then ... — Lasse V. Karlsen, Sep 22 '14 at 12:15
The size of the output is O(n*2^n), so there can't be an asymptotically faster method. — interjay, Sep 22 '14 at 12:21

FatalError · Accepted Answer · 2014-09-22T12:57:55.530

4

This if checks if bit j is set. For example, when j == 0 we're looking at (I'm using 8 bits for simplicity):

XXXXXXX? & 00000001

where X is "don't care", ? is what we want to check. Then when j == 1

XXXXXX?X & 00000010

In other words, it's a convenient way to check if a bit is set or unset, which determines whether the corresponding set element is included in the current set or not.

As for complexity, since there are 2^n sets in a power set, it's hard to imagine a faster algorithm for generating them all.

The reason this generates a power set is that a binary counter exhausts all combinations of n bit values, see the following for an example.

Example

set: {1, 2, 3}

counter    1<<j   intermediate result   final
    000    001    N/A
    000    010    N/A
    000    100    N/A
                                        {}
    001    001    3
    001    010    N/A
    001    100    N/A
                                        {3}
    < ... skip a few iterations ... >
    101    001    3
    101    010    N/A
    101    100    1
                                        {1,3}
    < ... etc ... >

edited Sep 22 '14 at 12:57

answered Sep 22 '14 at 12:21

FatalError

52,695
14
99
116

why to use left shifter < – starter Sep 22 '14 at 12:44
`1` is a value with all bits 0 except the least significant. Shifting left by `n` bits results in a value with only the `nth` bit set -- it allows for computing the appropriate bitmask based on the `j` counter's value. – FatalError Sep 22 '14 at 12:47
2

@FatalError you are good but would you explain with a simple example {a,b,c} things will be more clear – Sep 22 '14 at 12:51
Sure, that's not a bad idea... example added. – FatalError Sep 22 '14 at 12:58

score 1 · Answer 2 · answered Sep 22 '14 at 13:01

This code below will stop faster than the above algorithm.

Complexity wise, your assessment is correct as O(N*2^N) is the size of the output.

unsigned c;
for (counter = 0; counter < pow_set_size; counter++) {

    for (c = counter; c != 0; ) {
        if( c & 1 ) {
            printf("%c", set[j]);
        }
        c = c >> 1; // drop lsb
    }
    printf("\n");
}

Power set of a given set

2 Answers2