
October 30th, 2014, 10:37 AM
#1
Questions regarding a piece of code
Generate all subsets of a given set. In another words generate super set of a given set. Example Given set {1,2,3}. Output {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Here is the code,
Code:
void PrintCombination(int a[], int size)
{
int i, j, k;
int num;
num = 1<<size; // num for how many combinations
for(i=0;i<num;i++)
{
printf("{");
for(j=0;j<size;j++)
{
k = 1<<j;
if(k&i) // check if print kth digit
printf("%d ", a[j]);
}
printf("}\n");
}
}
What is the idea behind the code? Basically I couldn't relate the bit operations to the question. Especially why the statement 1<<size will give the number of the combinations? Thanks.

October 30th, 2014, 08:10 PM
#2
Re: Questions regarding a piece of code
Set has 2^n of subsets. I.e. any element of main set either exists or not in given subset. So algo just mask++. For instance, mask ={0,0,0} & set={1,2,3}, then we get subset0=mask & set = {}. Let's mask++, then mask={0,0,1}, then subset1={1} & so on.

October 31st, 2014, 03:00 AM
#3
Re: Questions regarding a piece of code
Originally Posted by LarryChen
What is the idea behind the code? Basically I couldn't relate the bit operations to the question. Especially why the statement 1<<size will give the number of the combinations?
It's because if there are size members in a set you can combine them in 2^size different ways. And 1<<size is the same as 2^size (because each leftshift equals a doubling).
The i variable will loop through the numbers from 0 to (2^size  1). If size is 3 that will be from 0 to 7. If you list the binary representations of those numbers you have,
0 : 000
1 : 001
2 : 010
3 : 011
4 : 100
5 : 101
6 : 110
7 : 111
Now the code interprets these binary numbers as bitsets. This means that if a bit is 1 the corresponding member in the set is present, otherwise not. For example if the rightmost bit is 1 then the set member "1" is present in the set, etcetera. You get,
000 : {}
001 : {1}
010 : {2}
011 : {1,2}
100 : {3}
101 : {1,3}
110 : {2,3}
111 : {1,2,3}
Last edited by razzle; October 31st, 2014 at 03:23 AM.

October 31st, 2014, 04:53 AM
#4
Re: Questions regarding a piece of code
Hi razzle!
You may want to delete your "empty" post here
Thank you
and
best wishes,
Victor
Victor Nijegorodov

November 1st, 2014, 09:56 PM
#5
Re: Questions regarding a piece of code
Originally Posted by razzle
It's because if there are size members in a set you can combine them in 2^size different ways. And 1<<size is the same as 2^size (because each leftshift equals a doubling).
The i variable will loop through the numbers from 0 to (2^size  1). If size is 3 that will be from 0 to 7. If you list the binary representations of those numbers you have,
0 : 000
1 : 001
2 : 010
3 : 011
4 : 100
5 : 101
6 : 110
7 : 111
Now the code interprets these binary numbers as bitsets. This means that if a bit is 1 the corresponding member in the set is present, otherwise not. For example if the rightmost bit is 1 then the set member "1" is present in the set, etcetera. You get,
000 : {}
001 : {1}
010 : {2}
011 : {1,2}
100 : {3}
101 : {1,3}
110 : {2,3}
111 : {1,2,3}
Really nice explanation. Thanks a lot.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
