Enumerating Supermasks

A supermask of $m$ is any mask $s$ with $m\subseteq s$ — every bit of $m$ is also set in $s$.

The loop

for (int s = mask; s < (1 << n); s = (s + 1) | mask) {
    // s runs over all supermasks of `mask` within n bits, increasing
}

Why it works

s + 1 increments, carrying through the trailing ones. ORing with mask re-establishes the required bits. The result is the next larger mask that still contains mask, and every supermask is visited exactly once.

Complexity

A mask of size $k$ has $2^{n-k}$ supermasks. Summing over all masks:

${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{n-k}=3^n,$

the same bound as submask enumeration — by symmetry (complement every mask).

Where supermasks are the natural direction

”How many sets contain this one”

// cnt[m] = number of input sets that are supersets of m
for (int m = 0; m < (1 << n); m++)
    for (int s = m; s < (1 << n); s = (s + 1) | m)
        cnt[m] += freq[s];

$O(3^n)$ — but the same thing is $O(2^{n}n)$ with superset-sum SOS DP:

for (int i = 0; i < n; i++)
    for (int m = 0; m < (1 << n); m++)
        if (!(m >> i & 1)) cnt[m] += cnt[m | (1 << i)];

Always prefer the SOS version. See SOS DP.

Minimal covering sets

“Find the smallest superset of $m$ satisfying property $P$” — enumerate supermasks in increasing order and stop at the first hit. Increasing numeric order is not increasing popcount order, so if you need the smallest cardinality, sort by popcount or BFS over the mask lattice.

Requirement propagation

When a constraint says “if you take these, you must also take those”, supermask enumeration is the natural iteration for closure computations.

Submasks vs supermasks

	Submasks	Supermasks
Loop	s = (s-1) & mask	s = (s+1) | mask
Order	decreasing	increasing
Count for $|m|=k$	$2^k$	$2^{n-k}$
Total over all masks	$3^n$	$3^n$
SOS direction	subset sum: if (m>>i&1) f[m] += f[m^(1<<i)]	superset sum: if (!(m>>i&1)) f[m] += f[m|(1<<i)]
Typical use	partitioning, splitting	covering, requirements

They are duals: enumerating supermasks of $m$ is enumerating submasks of $\overline{m}$ and complementing.

The Möbius/zeta transform view

Subset-sum and superset-sum are the zeta transforms of the subset lattice; SOS DP computes them in $O(2^{n}n)$. Their inverses are the Möbius transforms, obtained by replacing += with -=:

// inverse of the subset-sum transform
for (int i = 0; i < n; i++)
    for (int m = 0; m < (1 << n); m++)
        if (m >> i & 1) f[m] -= f[m ^ (1 << i)];

Zeta, pointwise multiply, inverse zeta = OR-convolution. The superset version gives AND-convolution, and FWHT gives XOR-convolution. Recognising which of the three you need is the key skill in this area.

See also: Enumerating Submasks · SOS DP · FWHT