Friday, January 4, 2013

Generating all subsets of a set

Sometimes, u need to enumerate all possible subsets of a size n as a sub-problem of some bigger problem. This can be done using bitmasks (ie) using bits of an integer to represent whether the element is there in the current subset(bit is 'set' or 1) or it is not in the current subset(bit is 'not set' or 0). C++ code with explanation follows:
int n=10; // size of set
int n2=1<<n; // set of size n has 2^n subsets
for(int i=1;i<n2;i++)
{
 mask = i;
 pos=n-1;
 while(mask>0)
 {
  if((mask&1)==1)
  {
  // Element at pos belongs to the current subset.
  }
  mask>>=1;
  pos--;
 }
}

No comments:

Post a Comment