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.

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.

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.

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

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.

#### Posting Permissions

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