JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase Re: Iterating Over All Subsets of a Set Revision History (2 edits)
 Re: Iterating Over All Subsets of a Set (response to post by hacker007) 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 hacker007) 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 zeroes, 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 hacker007) 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 zeroes, possibly) in this way: 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.