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.

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.

  • 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


Wiki ref “what is power set”


Related Contents to follow