Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
All subsets in increasing order | Reply
for(int sub = (super-1)&super;sub>0;sub=(sub-1)&super)
int incsub = ~sub & super; // the subset in increasing order :)

What do you think?
Re: All subsets in increasing order (response to post by zdravko_b) | Reply
    for ( int sub=0; (sub-=super)&=super; ) {

Or even
    for ( int sub=0; sub=sub-super&super; ) {
Re: All subsets in increasing order (response to post by venco) | Reply
After all this magic, is there a way to iterate over all subsets in increasing number of members? (non-decreasing number of bits with value 1 in each subset)
BITWISE (response to post by zdravko_b) | Reply
Guys...An Algorithmic Intensive Online Programming Competition is being
organized by Department of Computer Science and Engineering at Indian Institute of Technology(IIT) , Kharagpur, INDIA.

It's a must for Algo. Freaks.....Link is Following:
Re: BITWISE (response to post by mayank4u2) | Reply
OK, that's enough. Please STOP spamming!
Re: All subsets in increasing order (response to post by aminallam) | Reply
Can anyone shed light on how to generate iteratively all the subsets in the increasing order of bit count (number of ones in the bits)?
Re: All subsets in increasing order (response to post by chamiya) | Reply
"It is also possible to iterate over all the subsets of a particular subset (represented by a bit pattern), provided that you don't mind visiting them in reverse order (if this is problematic, put them in a list as they're generated, then walk the list backwards). The trick is similar to that for finding the lowest bit in a number. If we subtract 1 from a subset, then the lowest set element is cleared, and every lower element is set. However, we only want to set those lower elements that are in the superset. So the iteration step is just i = (i - 1) & superset."

All subsets of 7 will be 00000111 to 00000000 i guess.

But what we are trying to solve above?
Re: All subsets in increasing order (response to post by nishantmc) | Reply
The subsets don't always look that trivial. For example, the subsets of 21=00010101 are


What we want is a way to get the next element in this list in O(1).