Monday, February 11, 2013

Iterate through the Subsets of Subsets

Bit-mask DP

The main loop:
for (int mask = 0; mask < (1 << n); ++mask)
go(mask);
In the memoization process:
for (int i = mask; i != 0; i = (i - 1) & mask)
// the status transformation


For a certain bit which is 1 in mask, all possible combinations of lower 1 bits are enumerated, ending in all 0s. Then this bit becomes 0 with other initial lower 1 bits recovered by the bit-wise and. Again combinations of those bits are enumerated, ending in all 0s, while this bit remains 0.

Complexity

The overall time complexity measured in the number of transformations is $latex \sum_{i=0}^{n}(\binom{n}{i} \sum_{j=0}^{i}\binom{i}{j}) - 2^n = 3^n - 2^n$.

No comments:

Post a Comment