CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Questions regarding a piece of code

1. Senior Member Join Date
Jul 2005
Posts
1,030

## 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.  Reply With Quote

2. Member Join Date
Feb 2013
Posts
58

## 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.  Reply With Quote

3. Member +  Join Date
Jul 2013
Posts
576

## 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.  Reply With Quote

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  Reply With Quote

5. Senior Member Join Date
Jul 2005
Posts
1,030

## 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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 