

Revision History 

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 ndigit ternary number (with leading zeros, possibly): Put a 0 in the ith 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.


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 ndigit ternary number (with leading zeroes, possibly): Put a 0 in the ith 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.


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 ndigit ternary number (with leading zeroes, possibly) in this way: Put a 0 in the ith 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.

