# Power gain of a given set

Given a set, I want to display all subsets of it (its cardinality set). I 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 cannot figure out why this part is being used

`````` if(counter & (1<<j))
```

```

what is its meaning?

Time complexity for this algorithm `O(n2^n)`

is there a better method?

+3

source to share

This one `if`

checks if a bit is set `j`

. For example, when `j == 0`

we look (I'm using 8 bits for simplicity):

``````XXXXXXX? & 00000001
```

```

where `X`

"doesn't care" `?`

is what we want to test. Then when`j == 1`

``````XXXXXX?X & 00000010
```

```

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

In terms of complexity, since there are `2^n`

sets in a cardinality set, it is difficult to imagine a faster algorithm for creating them.

The reason the power set is generated is because the binary counter runs out of all bit value combinations `n`

, see below 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 ... >
```

```
+4

source

This code below stops faster than the specified algorithm.

Complexity, your estimate is correct since 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");
}
```

```
+1

source

All Articles