Lets try PowerSet!!

Friends lets go little mix and match. Lets try our mind with some algorithms.

In Mathematics we all would have studied Sets, Lets try to print the PowerSet for a given set S.

Now what is a Power set, lets try to understand with an example.

If S is the set {a, b, c}, then the subsets of S are:

{} 

{a}

{b}

{c}

{a, b}

{a, c}

{b, c}

{a, b, c}

and hence the power set of S is {{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}

For more on Sets, you can visit some sites on Maths, but for the algorithm of PowerSet we are going to discuss above information is enough.

Lets try to represent the power set by below process. 

    a    b    c        decimal number        Sub Set

    0    0    0                  1                        {}
    0    0    1                  2                        {c}
    0    1    0                  3                        {b}
    0    1    1                  4                        {b,c}
    1    0    0                  5                        {a}
    1    0    1                  6                        {a,c}
    1    1    0                  7                        {a,b}
    1    1    1                  8                        {a,b,c}

                                                  POWER SET :  { {}, {c}, {b}, {b,c}, {a}, {a,c}, {a,b}, {a,b,c} }

 public class PowerSet {

      public static char[] input = {'A','B','C'};

      public static void main(String[] args) {
           printPowerSet();
      }

      public static void printPowerSet(){
           int N = input.length;
           int twoPowN = 1<<N;
           for(int i = 0 ; i < twoPowN ; i++){
                System.out.print("{");
                for(int j = 0; j < N; j++){

                     // i goes from 000, 001, 010, 011, 100, 101, 110, 111 (111 is twoPowN-1)  
                     // j goes from 0,1,2 : 000,001,010  
                     // Quest. How to know if jth bit of i is set ? : Ans. Perform AND of i with 1<<j   
                     // 001<<0 == 001  
                     // 001<<1 == 010  
                     // 001<<2 == 100  
                     boolean isJthBitOfISet = (i & (1<<j)) != 0; // this will be 0,2,4
                     if(isJthBitOfISet){
                          // print the jth element  
                          System.out.print(" " +input[j]);
                     }
                }
                System.out.println(" }");
           }
      }
 }

Output is
{ }
{ A }
{ B }
{ A B }
{ C }
{ A C }
{ B C }
{ A B C }

Try coding this on your own and you will get the concept!!. Follow this place for more stuff...

Happy coding!!