# what is power set explain with example

*what is power set explain it with example?*

Let me ask one question. What is set? Answer is “a set is collection of distinct objects”. Now let us define power set. A power set is all set of subsets. For example if a set S = {1,2,3} then its power set is all subsets of set S and those subsets are {},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}. {} is an empty set. every empty set is a subset of any set S.

*How to generate a power set of a given set S*

Let us observe the power set of set S = {1,2,3}, they are as below and total subsets are 8.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} |

*So we can easily observe that there are 3 elements in our set S and there are 8 ( 2 to the power 3 ) subsets in our power set. Now Let us see below observation.
*

1 2 3 4 5 6 7 8 9 10 |
S={1,2,3} 0 0 0 0 { no element selected } {} 1 0 0 1 { 3rd element in set S is selected } {1} 2 0 1 0 { 2nd element in set S is selected } {2} 3 0 1 1 { 1st & 2nd elements in set S are selected } {1,2} 4 1 0 0 { 3rd element in set S is selected } {3} 5 1 0 1 { 3rd &1st elements in set S are selected } {1,3} 6 1 1 0 { 2nd & 3rd elements in set S are selected } {2,3} 7 1 1 1 { all element in set S are selected } {1,2,3} (decimal) (binary) |

*From above we can see that if we iterate from i= 0 to i = 2^3 -1 (where 3 is number of elements in set S) and check the index of set bit of binary equivalent of i, then we can select the elements of set S={1,2,3}. For example if i=6, its binary equivalent is 110, so the second and third bit positions are set, and at this level we would include {2,3} subsets in our power set.*

*C program to generate a power set of a given set S*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<stdio.h> #include<math.h> #define N 3 int arr_set[N] = { 1, 2, 3 }; int main() { // iterate from 0 to 2^N - 1 for (int i = 0; i < pow(2, N); i++) { // check which index of binary number of decimal i // is set for (int j = 0; j < N; j++) { if (i & (1 << j)) // check if jth bit is set { printf("%d ", arr_set[j]); } } printf("\n"); } return 0; } |

Ref:

## Leave a Reply