Enumeración de submáscaras

Enumerar todas las submáscaras de una máscara dada

Dada una máscara de bits $m$, se quiere iterar de forma eficiente por todas sus submáscaras, es decir, máscaras $s$ en las que solo están activados bits que ya estaban incluidos en la máscara $m$.

Consideremos la implementación de este algoritmo, basada en trucos con operaciones de bits:

int s = m;
while (s > 0) {
 ... se puede usar s ...
 s = (s-1) & m;
}

o, usando una sentencia for más compacta:

for (int s=m; s; s=(s-1)&m)
 ... se puede usar s ...

En ambas variantes del código, la submáscara igual a cero no se procesará. Podemos procesarla fuera del bucle, o usar un diseño menos elegante, por ejemplo:

for (int s=m; ; s=(s-1)&m) {
 ... se puede usar s ...
 if (s==0)  break;
}

Examinemos por qué el código anterior visita todas las submáscaras de $m$, sin repetición, y en orden descendente.

Supongamos que tenemos una máscara de bits actual $s$, y queremos pasar a la siguiente máscara de bits. Al restarle una unidad a la máscara $s$, eliminamos el bit activado más a la derecha y todos los bits a su derecha se vuelven 1. Luego quitamos todos los bits uno “de más” que no están incluidos en la máscara $m$ y por lo tanto no pueden formar parte de una submáscara. Hacemos esa eliminación usando la operación bit a bit (s-1) & m. Como resultado, “recortamos” la máscara $s-1$ para determinar el valor más alto que puede tomar, es decir, la siguiente submáscara después de $s$ en orden descendente.

Así, este algoritmo genera todas las submáscaras de esta máscara en orden descendente, realizando solo dos operaciones por iteración.

Un caso especial es cuando $s = 0$. Después de ejecutar $s-1$ obtenemos una máscara con todos los bits activados (representación de bits de -1), y después de (s-1) & m tendremos que $s$ será igual a $m$. Por lo tanto, hay que tener cuidado con la máscara $s = 0$: si el bucle no termina en cero, el algoritmo puede entrar en un bucle infinito.

Iterar por todas las máscaras con sus submáscaras. Complejidad $O(3^n)$

En muchos problemas, especialmente los que usan programación dinámica con máscaras de bits, se quiere iterar por todas las máscaras de bits y, para cada máscara, iterar por todas sus submáscaras:

for (int m=0; m<(1<<n); ++m)
	for (int s=m; s; s=(s-1)&m)
 ... s y m ...

Demostremos que el bucle interno ejecutará un total de $O(3^n)$ iteraciones.

Primera demostración: Consideremos el $i$-ésimo bit. Hay exactamente tres opciones para él:

1. no está incluido en la máscara $m$ (y por lo tanto no está incluido en la submáscara $s$),
2. está incluido en $m$, pero no está incluido en $s$, o
3. está incluido tanto en $m$ como en $s$.

Como hay un total de $n$ bits, habrá $3^n$ combinaciones distintas.

Segunda demostración: Nótese que si la máscara $m$ tiene $k$ bits activados, entonces tendrá $2^k$ submáscaras. Como hay un total de $\binom{n}{k}$ máscaras con $k$ bits activados (véase coeficientes binomiales), entonces el número total de combinaciones para todas las máscaras será:

$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$

Para calcular este número, nótese que la suma anterior es igual a la expansión de $(1+2)^n$ usando el teorema del binomio. Por lo tanto, hay $3^n$ combinaciones, como queríamos demostrar.

Problemas de práctica

• Atcoder - Close Group 
• Codeforces - Nuclear Fusion 
• Codeforces - Sandy and Nuts 
• Uva 1439 - Exclusive Access 2 
• UVa 11825 - Hackers’ Crackdown