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--) {
            mask = 1 << j;
            if (i & mask)
                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[1]);
    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][0] == '#'))
            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.