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?
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 whenj == 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 ... >
source to share
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");
}
source to share