JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set [ 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 64the 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<<
 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<
 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< 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 elementsfor (int i = 0; i < (1<< m ? i+1 : (i|(i-1))+1){ ...}why i can't modify it as below?for (int i = 0; i < (1<<=m; i++){ ...}
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Iterating Over All Subsets of a Set Previous Thread  |  Next Thread [ 1 2 ]    NEXT >