finding all subset of given set using bitmask

general
, ,
1

how to find all the subsets of a given set using bit manipulation can someone explain

2

There is beautiful tutorial here. You can check it here once- this codehef tutorial

Though it is well explained in the above tutorial I will put my words here

suppose this is the set
{ 1 2 3 ... N }
Now you can consider creating all its subset
For each element there is 2 possibilities either keep it or leave it
This way there are 2^N possible cases.
For each of this case you can consider the binary representation of the number
if(j th bit is set include it)
else
 leave it.

That’s how I understood it. Take a small example

   {1 2 3}
   {1 2 3}   1 1 1
   {1 2  }   1 1 0
   {1   3}   1 0 1
   {1    }   1 0 0
   {  2 3}   0 1 1
   {  2  }   0 1 0
   {    3}   0 0 1
   {     }   0 0 0--->empty set
1 Like
3

Let us assume you have array as {1,2,3} now all the subsets of this array can be generated by using bitmask. A bitmask is combination of 0 and 1. Here n=3 i.e. total elements = 3 in the array so you write a loop of i ranging from 0 to 2^3-1 i.e. 2^n-1, Convert every value of i to binary i.e. 001,010 and corresponding to these 0 and 1 you include or exclude that value of array. For eg here->

000 No elements

001 include third element of array

010 include second element of array
and so on till 111 i.e. include all elemnts of array. Now this algo can be applied by your basic decimal to binary conversion of each value of i and corresponding to the 1 you can pick those elements from array. The bitmask code is a simplification and fast implementation of it which you can get from this link or this

1 Like
4


This link will help you understand it.

1 Like
5

how should use bitmask if N>=100 then we can not store 2^100??

6

http://www.geeksforgeeks.org/power-set/ for more detail…

Array bit Stored approach
int Arr[N]={0};
while(A[0]<=1)
{
//use present combination
A[N-1]++;

for(int i=N-1;i>0;i--){
   if(A[i]>1){
           A[i]=0;
           A[i-1]++;
   }
  else break;
}

}

}

more optimized method required. Please Share

7

http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/

this sure clears things up,have a look at it !!