algorithmmathpowerset

How to generate a power set of a given set?

I am studying for an interview and I stumbled upon this question online under the "Math" category.

Generate power set of given set:

int A[] = {1,2,3,4,5};  
int N = 5; 
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) { 
 for ( int j = 0; j < N; j++) {
  if ( (i >> j) & 1 ) 
      cout << A[j]; 
   } 
 cout <<endl;

 }

Please I do not want an explicit answer. I just want clarifications and hints on how to approach this problem.

I checked power set algorithm on google and I still do not understand how to address this problem.

Also, could someone reiterate what the question is asking for.

Thank you.

Solution

  • Power set of a set A is the set of all of the subsets of A.

    Not the most friendly definition in the world, but an example will help :

    Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2}

    Thus, the power set is {{}, {1}, {2}, {1, 2}}

    To generate the power set, observe how you create a subset : you go to each element one by one, and then either retain it or ignore it.

    Let this decision be indicated by a bit (1/0).

    Thus, to generate {1}, you will pick 1 and drop 2 (10).

    On similar lines, you can write a bit vector for all the subsets :

    To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N different decisions, corresponding to 2^N different subsets.

    See if you can pick it up from here.