Medio · máscara de bits

Generar subconjuntos

Toma el conjunto {1, 2, 3} y pregunta por cada elemento: ¿dentro o fuera? Es una pregunta de sí/no, y una fila de sí/no es un número binario. n elementos dan 2^n subconjuntos — todos alcanzables contando de 1 a 2^n − 1.

En una frasePara cada máscara de 1 a 2^n − 1, escribe cada i cuyo bit esté a 1 (pruébalo con <code>mask % 2</code> y luego <code>mask /= 2</code>) — sin recursión.

El problema

Entrada: Un entero n (1 ≤ n ≤ 8).

Salida: Todos los subconjuntos no vacíos de {1, …, n}, uno por línea, valores en orden creciente, subconjuntos ordenados por su máscara binaria (para n = 3: 1, 2, 1 2, 3, 1 3, 2 3, 1 2 3).

Ejemplos:

Entrada	Salida
`2`	`1 2 1 2`
`3`	`1 2 1 2 3 1 3 2 3 1 2 3`

El subconjunto vacío es la máscara 0, y el juez no quiere una primera línea en blanco — empieza a contar en 1. Los valores de cada subconjunto salen en orden creciente si pruebas los bits de i = 1 hacia arriba.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — El bit i significa «i está dentro»

Acuerda que el bit i−1 de la máscara (contando desde 0) decide si se escribe el valor i. La máscara 0b101 con n = 3 es el subconjunto {1, 3}. Fijada la convención, escribir un subconjunto es recorrer sus bits.

Pista 2 — Descodifica los bits con % y /

No necesitas los operadores de desplazamiento: copia la máscara en un temporal y pélala — if (m % 2 == 1) escribe i; y después m /= 2; mientras i va de 1 a n. Es exactamente el bucle de trocear dígitos de Binario, apuntado a bits en vez de a dígitos decimales.

Pista 3 — Construye 2^n multiplicando

Empieza limit en 1 y duplícala n veces (limit *= 2 en un bucle). Las máscaras van de 1 a limit - 1. Con n = 8 son 255 subconjuntos — 2^n crece deprisa, y el problema solo es imprimible porque el juez mantiene n pequeño.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;

    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        bool first = true;
        for (int i = 1; i <= n; i++) {
            if (m % 2 == 1) {
                if (!first) cout << " ";
                cout << i;
                first = false;
            }
            m /= 2;
        }
        cout << endl;
    }
    return 0;
}

El truco de subconjunto-como-máscara es la columna del fuerza bruta: con n ≤ 20, probar los 2^n subconjuntos es un plan legítimo, y más adelante alimenta la PD con máscaras. Fíjate en lo que no hiciste falta: recursión. El bucle de contar de Binario y este son la misma máquina apuntando a escalas distintas.

Análisis profundo

Por qué funciona

Un subconjunto de {1..n} es una decisión sí/no por elemento, y una fila fija de sí/no es un número binario. Contar máscaras de 1 a 2^n−1 enumera entonces cada subconjunto no vacío exactamente una vez, y probar el bit i−1 (m % 2, luego m /= 2) dice si el valor i está dentro.

El coste

O(2^n × n) de tiempo — cada máscara se descodifica en O(n) — y O(1) de espacio extra aparte de los contadores. n = 10 son 10.240 líneas; n = 20 ya son 20 millones: la fuerza bruta con máscaras tiene un techo duro.

Dónde falla

Empezar el bucle de máscaras en 0 imprime el subconjunto vacío como una primera línea en blanco que el juez rechaza — empieza en 1.
Olvidar el temporal: hacer m /= 2 en la misma expresión que prueba m % 2 se come el bit antes de leerlo. Copia la máscara y luego pélala.
Escribir el espacio después del último valor en vez de entre valores — el juez recorta el final de línea, pero un espacio antes del primer número es respuesta errónea, no cuestión de estilo.

Siguiente paso

El mismo bucle de % y / apuntado a números decimales es Binario; apuntado a los bits en 1 de un número, Contar bits 1. Un bucle, tres problemas.

Dos cosas para recordar

Un subconjunto de {1..n} es un número de n bits; el bit i = «i está dentro».
2^n es el presupuesto de la fuerza bruta: n = 10 bien, n = 20 un millón, n = 40 imposible.

🐞 Esta versión falla: ábrela y pruébala

Divide antes de probar: m /= 2 en la misma línea se come el bit que acababa de leer

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int limit = 1;
    for (int i = 0; i < n; i++) limit *= 2;
    for (int mask = 1; mask < limit; mask++) {
        int m = mask;
        for (int i = 1; i <= n; i++) {
            m /= 2;                  // bug: eats bit 0 before testing
            if (m % 2 == 1) cout << i << " ";
        }
        cout << endl;
        // also: trailing space instead of separators
    }
    return 0;
}