Print Power Set of a Set of character.
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}}.
If S has n elements in it then P(s) will have 2^n elements
Method 1:
Input: Set[], set_size 1. Get the size of power set powet_set_size = pow(2, set_size) 2 Loop for counter from 0 to pow_set_size (a) Loop for i = 0 to set_size (i) If ith bit in counter is set Print ith element from set for this subset (b) Print seperator for subsets i.e., newline
#include <stdio.h> #include <math.h> voidprintPowerSet(char*set, intset_size) { /*set_size of power set of a set with set_size n is (2**n -1)*/ unsigned intpow_set_size = pow(2, set_size); intcounter, 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*/ intmain() { charset[] = {'a','b','c'}; printPowerSet(set, 3); getchar(); return0; }
Method 2: We can use Recursion and with understanding of Binary Tree , we can format it.
Example :
{a,b,c} print set= abc / \ / \ / \ {a,b} {b,c} print set = ab,bc /\ /\ / \ / \ {a} {b} {b} {c} print set
void printPowerSet(char *set, int l , int h , int size) { int i=l; for(i=l;i<=h;i++){printf("%c",set[i]);} printf("n"); if(l+1 < size){ printPowerSet(set,l+1,h,size); } if(h-1 >= 0 ){ printPowerSet(set,l,h-1,size); } }//printpowerset int main(void) { char set[] = {'a','b','c','d'}; printPowerSet(set,0,3,4 ); getchar(); return 0; }
I have run it here…
http://ideone.com/e.js/faEPpM