Power Set


Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.\n\nIf S has n elements in it then P(s) will have 2^n elements\n\n\nAlgorithm:\n\nInput: Set[], set_size\n1. Get the size of power set\n powet_set_size = pow(2, set_size)\n2 Loop for counter from 0 to pow_set_size\n (a) Loop for i = 0 to set_size\n (i) If ith bit in counter is set\n Print ith element from set for this subset\n (b) Print seperator for subsets i.e., newline\nExample:\n\nSet = [a,b,c]\npower_set_size = pow(2, 3) = 8\nRun for binary counter = 000 to 111\n\nValue of Counter Subset\n 000 -> Empty set\n 001 -> a\n 011 -> ab\n 100 -> c\n 101 -> ac\n 110 -> bc\n 111 -> abc.


#include <stdio.h>
#include <math.h>
#include <string.h>
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++)
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
            printf("%c", set[j]);
/*Driver program to test printPowerSet*/
int main()
    char set[20] ;
    printPowerSet(set, strlen(set));
    return 0;

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.