-
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 left-shift 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 bit-sets. 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 left-shift 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 bit-sets. 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
|