CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    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. #2
    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. #3
    Join Date
    Jul 2013
    Posts
    576

    Re: Questions regarding a piece of code

    Quote Originally Posted by LarryChen View Post
    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. #4
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,396

    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

  5. #5
    Join Date
    Jul 2005
    Posts
    1,030

    Re: Questions regarding a piece of code

    Quote Originally Posted by razzle View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured