JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Re: Iterating Over All Subsets of a Set (response to post by ZuBruce) | Reply
You can always use a BigInteger. Anyway iterating over such large sets is going to be too slow.
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
the mapping from bit to subset is limited.
when the set size is more than 32 or 64
the subset number will be more than Integer.MIN_VALUE or Long.MAX_VALUE.
Re: Iterating Over All Subsets of a Set (response to post by d@rk_sh@dow) | Reply
You can either use the method described above in Discussion (for m or less bits). Or you can use a more direct method described in NextBitPermutation here: http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
Re: Iterating Over All Subsets of a Set (response to post by holomorph) | Reply
How can we extend the idea of to generate subsets with k elements. I can simply iterate over all 1<<n states and counting the number of set bits in each of the subset. If it equals k then I'll take into consideration. Is there any better way of doing this ? Can't we loop over only those sets which have k set bits directly instead of iterating over all 1><<n sets ?
Re: Iterating Over All Subsets of a Set (response to post by sjsupersumit) | Reply
It's checking if bit k of i is set, since 1<<k == 2^k.>
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
can you please explain what this line is doing " if ((i&(1<<k)) > 0) " ?
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
the cookbook example is good and its helping me. Can u site some problem of this type as i am learning how to program.

Thank in advance
Re: Iterating Over All Subsets of a Set (response to post by puneetm) | Reply
You can change to another representation of the set: (element,count). The set is then represented as {(1,2),(2,1),(3,1),(4,3)}. For each element, loop through each possible count. In this case, there are 3*2*2*4 subsets to loop through (including the empty set).
Re: Iterating Over All Subsets of a Set (response to post by puneetm) | Reply
I don't know how to do that. I guess you could keep a HashSet of all subsets that you have seen (you need a good hash function). If you meet a subset that you have already seen then skip it.
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
How will the method to go over all subsets of a set change if the numbers are not unique. For example if we need to find subsets of {1,1,2,3,4,4,4} such that no set is repeated i.e. We don't need to have {1} twice. But {1,1} will be a valid set.

What is the best way to do it?
Re: Iterating Over All Subsets of a Set (response to post by hacker007) | Reply
There are exactly 3^n pairs (A,B) where B is a set of elements of {1, ..., n} and A is a subset of B. To see this, notice that each pair of sets like this can be associated to a n-digit ternary number (with leading zeros, possibly): Put a 0 in the i-th position if i is in neither A nor B, an 1 if i is in B but not A, and a 2 if i is in both sets. Since this is clearly a bijection, we've proved the result.

If you take O(1) time per subset while iterating, you then have a O(3^n) algorithm for iterating over all pairs as above.
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
You said "Another trick is to iterate over all the subsets of a subset in O(3^n) time", can you explain a bit more how O(3^n) was obtained? Thanks.
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
Another useful bit twiddling hack is gospers hack, which calculates the next greater number, that has the same number of bits set in binary representation. This can be used in a loop, to run through those subsets with k elements.
Re: Iterating Over All Subsets of a Set (response to post by savon_cn) | Reply
First of all your code tests all 2^n elements, which makes it much slower. Secondly your code will terminate as soon as it reaches a number with more than m bits set to 1. This means that it will not find all subsets with no more than m elements, only some of them.
Re: Iterating Over All Subsets of a Set (response to post by dimkadimon) | Reply
// iterate over all the subsets with no more than m elements
for (int i = 0; i < (1<<n); i=Integer.bitCount(i) >< m ? i+1 : (i|(i-1))+1)
{
...
}

why i can't modify it as below?

for (int i = 0; i < (1<<n) && Integer.bitCount(i)><=m; i++)
{
...
}
[ 1 2 ]    NEXT >

RSS