Bits make iterating through all the subsets of a set very easy. A set can be considered as a bit vector and we can iterate through every subset by incrementing from zero to the value 2^k ( where k is the number of elements in the set and therefore 2^k is the total number of subsets there will be. Including the empty subset).
For eg. let there be a set : [ a, b, c]. It's subsets can be generated by iterating through from the bit vector 000 to 111 (7). There are in total 2^3 i.e. 8 iterations and therefore 8 subsets.
000 { }
001 { a }
010 { b }
011 { a, b }
100 { c }
101 { a, c }
110 { b, c }
111 { a, b, c }
The following piece of code does the same :
char[] name={'a', 'b', 'c'};
//All the subsets. Iterating from 0 to 1<<k (left shifting by 2 i.e. 2^k)
for(int i=0;i<1<<name.length);i++)
{
char[] subset=new char[name.length];
//Checking for each bit in a particular iteration
for(int k=0; k<name.length;k++){
if(((1<<k) & i) != 0){
subset[k]=name[k];
}
}
System.out.println(Integer.toBinaryString(i)+" "+new String(subset));
}
Once we get the hang of it we can play around with it. Like with the following code we can limit the maximum number of elements that we want in our subsets :
//Subsets with at max m elements
for(int i=0; i < (1<<name.length);i=Integer.bitCount(i)< m ?i+1:(i|(i-1))+1){
char[] subset=new char[name.length];
for(int k=0; k<name.length;k++){
if(((1<<k) & i) > 0){
subset[k]=name[k];
}
}
System.out.println(new String(subset));
}
Here the iterative part in the outer for loop keeps the number of '1's in the bit vector at most m and therefore our subsets have elements <= m.
For eg. let there be a set : [ a, b, c]. It's subsets can be generated by iterating through from the bit vector 000 to 111 (7). There are in total 2^3 i.e. 8 iterations and therefore 8 subsets.
000 { }
001 { a }
010 { b }
011 { a, b }
100 { c }
101 { a, c }
110 { b, c }
111 { a, b, c }
The following piece of code does the same :
char[] name={'a', 'b', 'c'};
//All the subsets. Iterating from 0 to 1<<k (left shifting by 2 i.e. 2^k)
for(int i=0;i<1<<name.length);i++)
{
char[] subset=new char[name.length];
//Checking for each bit in a particular iteration
for(int k=0; k<name.length;k++){
if(((1<<k) & i) != 0){
subset[k]=name[k];
}
}
System.out.println(Integer.toBinaryString(i)+" "+new String(subset));
}
Once we get the hang of it we can play around with it. Like with the following code we can limit the maximum number of elements that we want in our subsets :
//Subsets with at max m elements
for(int i=0; i < (1<<name.length);i=Integer.bitCount(i)< m ?i+1:(i|(i-1))+1){
char[] subset=new char[name.length];
for(int k=0; k<name.length;k++){
if(((1<<k) & i) > 0){
subset[k]=name[k];
}
}
System.out.println(new String(subset));
}
Here the iterative part in the outer for loop keeps the number of '1's in the bit vector at most m and therefore our subsets have elements <= m.