Power Set

QUESTION

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.

ANSWER

#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]);
       }
       printf("\n");
    }
}
 
/*Driver program to test printPowerSet*/
int main()
{
    char set[20] ;
  scanf("%s",set);
    printPowerSet(set, strlen(set));
 
    getchar();
    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.

Powered By
CHP Adblock Detector Plugin | Codehelppro