JOIN
Get Time
forums  Revision History
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.