## Sunday, 14 July 2013

### Simple Power Set Generator

Currently I was trying to code some algorithm that one of my friend told me to do. In that algorithm I needed the code of a power-set generator. I first tried to code in my own way but it proved to be not so much simple. Then I found another simple logic to generate power-set. Logic is simple if you want the power-set of a set with n number of elements then just generate all the combination of n boolean variables.

Suppose you want the power-set of 3 variables a,b,c. Then take 3 boolean variables and generate their all their possible combination. For 3 variables it will be:
```+---------+---------+----------+---------+
|Index    |pos-2    |pos-1     |pos-0    |
+---------+---------+----------+---------+
| 0       |   0     |   0      |  0      |
+---------+---------+----------+---------+
| 1       |   0     |   0      |  1      |
+---------+---------+----------+---------+
| 2       |   0     |   1      |  0      |
+---------+---------+----------+---------+
| 3       |   0     |   1      |  1      |
+---------+---------+----------+---------+
| 4       |   1     |   0      |  0      |
+---------+---------+----------+---------+
| 5       |    1    |   0      |  1      |
+---------+---------+----------+---------+
| 6       |   1     |   1      |  0      |
+---------+---------+----------+---------+
| 7       |   1     |   1      |  1      |
+---------+---------+----------+---------+
```
Now print 'a' when there is an 1 in pos-0 and 'b' when there is an 1 in pos-1 and 'c' when there is an 1 in pos-2 and all position is 0 means NULL set. Now for 3 element set {a,b,c}  power-set will be :
```
{
{NULL}, [000: all positions are 0]
{a},    [001: only pos-0 is 1 others are 0]
{b},    [010: only pos-1 is 1 ]
{a,b}   [011: pos-0 and pos-1 is 1]
{c},    [100: only pos-3 is 1]
{a,c},  [101: pos-1 and pos-2 is 1]
{b,c},  [110: pos-1 and pos-2 is 1]
{a,b,c} [111: all positions are 1]
}```

Now the problem is how to generate these boolean variables combination. Here we can use bitwise operator. We only need right/left shift operator and the  bitwise AND(&) operator for masking purpose. Actually we will iterate a loop from 0 to (2^n) where n is the number of elements in the set and then scanning n leftmost element of each loop count and check whether it is 1 or 0.
For 3 variables we will use a loop i:=0 to 7 and then at each iteration we will scan binary representation (using masking
operation) of i and check leftmost n binary position for 0 or 1.

Code in C:
```/*It needs one command line argument which is the number of elements in the set*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

char **get_powerset(char *ptr, int k)
{
int i, j, num_element, mask, l, val;
char **power_set;
num_element = pow(2, k);
power_set = malloc(sizeof(char *) * (num_element));
for (i = 0; i < num_element; i++) {
power_set[i] = malloc(sizeof(char) * k);
memset(power_set[i], '#', (sizeof(char) * k));
}
for (i = num_element - 1; i >= 0; i--) {
l = 0;
for (j = k - 1; j >= 0; j--) {
power_set[i][l++] = ptr[j];
}
}
return power_set;
}

int main(int argc, char **argv)

{
int i, num_element, k, j, num_item;
char **power_set, *ptr;
num_item = atoi(argv);
ptr = malloc(sizeof(char) * num_item);
for (i = 0; i < num_item; i++) {
printf("Enter %d no. element:", i);
scanf(" %c", &ptr[i]);
}
power_set = get_powerset(ptr, num_item);
num_element = pow(2, num_item);
printf("\nPower Set is==>\n\n");
for (i = 0; i < num_element; i++) {
printf("{");
for (j = 0; (power_set[i][j] != '#') && (j < num_item); j++) {
printf("%c,", power_set[i][j]);
}
if (i == 0 && (power_set[i] == '#'))
printf("NULL,");
printf("\b}");
printf("\n");
}
return 0;
}
```
Description:

The function "get_powerset" returns an 2-d array of size (2^n) X n where each row contains one element of the power-set. As the length of each element of the power set is not constant so we have used # as terminator except the element that contains all the element of the set. For example if the set is {1,2,3} then this function will return the below 2-d array:
```+----+----+----+
|#   |    |    |  {NULL}
+----+----+----+
|  1 | #  |    |  {1}
+----+----+----+
|  2 |#   |    |  {2}
+----+----+----+
|  2 | 1  | #  |  {2,1}
+----+----+----+
|  3 | #  |    |  {3}
+----+----+----+
|  3 | 1  | #  |  {3,1}
+----+----+----+
|  3 | 2  | #  |  {3,2}
+----+----+----+
|  3 | 2  | 1  |  {3,2,1}
+----+----+----+
```
One problem with this logic is that it is limited to the size of the memory allocated to the data-type of i.