Generar todas las $K$-combinaciones

En este artículo discutiremos el problema de generar todas las $K$-combinaciones. Dados los números naturales $N$ y $K$, y considerando un conjunto de números de $1$ a $N$. La tarea es obtener todos los subconjuntos de tamaño $K$.

Generar la siguiente $K$-combinación lexicográfica {data-toc-label=“Generar la siguiente K-combinación lexicográfica”}

Primero las generaremos en orden lexicográfico. El algoritmo para esto es sencillo. La primera combinación será ${1, 2, …, K}$. Ahora veamos cómo hallar la combinación que sigue inmediatamente a esta, lexicográficamente. Para ello, consideramos nuestra combinación actual, y hallamos el elemento más a la derecha que aún no ha alcanzado su valor más alto posible. Una vez hallado este elemento, lo incrementamos en $1$, y asignamos el valor válido más bajo a todos los elementos posteriores.

bool next_combination(vector<int>& a, int n) {
    int k = (int)a.size();
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

Generar todas las $K$-combinaciones tales que las combinaciones adyacentes difieren en un elemento {data-toc-label=“Generar todas las K-combinaciones tales que las combinaciones adyacentes difieren en un elemento”}

Esta vez queremos generar todas las $K$-combinaciones en un orden tal que las combinaciones adyacentes difieran exactamente en un elemento.

Esto se puede resolver usando el código de Gray: Si asignamos una máscara de bits a cada subconjunto, entonces generando e iterando sobre estas máscaras con códigos de Gray, podemos obtener nuestra respuesta.

La tarea de generar $K$-combinaciones también se puede resolver usando códigos de Gray de otra manera: generar códigos de Gray para los números de $0$ a $2^N - 1$ y dejar solo aquellos códigos que contienen $K$ $1$s. El hecho sorprendente es que en la secuencia resultante de $K$ bits activados, cualesquiera dos máscaras vecinas (incluyendo la primera y la última máscara, vecinas en sentido cíclico) diferirán exactamente en dos bits, que es nuestro objetivo (quitar un número, añadir un número).

Demostrémoslo:

Para la demostración, recordamos el hecho de que la secuencia $G(N)$ (que representa el $N$^ésimo código de Gray) se puede obtener como sigue:

$$G(N) = 0G(N-1) \cup 1G(N-1)^\text{R}$$

Es decir, consideramos la secuencia de código de Gray para $N-1$, y prefijamos $0$ antes de cada término. Y consideramos la secuencia de código de Gray invertida para $N-1$ y prefijamos un $1$ antes de cada máscara, y concatenamos estas dos secuencias.

Ahora podemos producir nuestra demostración.

Primero, demostramos que la primera y la última máscara difieren exactamente en dos bits. Para ello, basta notar que la primera máscara de la secuencia $G(N)$ será de la forma $N-K$ $0$s, seguidos de $K$ $1$s. Como el primer bit se pone como $0$, después de lo cual siguen $(N-K-1)$ $0$s, después de lo cual siguen $K$ bits activados, y la última máscara será de la forma $1$, luego $(N-K)$ $0$s, luego $K-1$ $1$s. Aplicando el principio de inducción matemática, y usando la fórmula para $G(N)$, se concluye la demostración.

Ahora nuestra tarea es mostrar que cualesquiera dos códigos adyacentes también difieren exactamente en dos bits; podemos hacerlo considerando nuestra ecuación recursiva para la generación de códigos de Gray. Asumamos que el contenido de las dos mitades formadas por $G(N-1)$ es verdadero. Ahora necesitamos probar que el nuevo par consecutivo formado en la unión (por la concatenación de estas dos mitades) también es válido, es decir, que difieren exactamente en dos bits.

Esto se puede hacer, porque conocemos la última máscara de la primera mitad y la primera máscara de la segunda mitad. La última máscara de la primera mitad sería $1$, luego $(N-K-1)$ $0$s, luego $K-1$ $1$s. Y la primera máscara de la segunda mitad sería $0$, luego seguirían $(N-K-2)$ $0$s, y luego $K$ $1$s. Así, comparando las dos máscaras, hallamos exactamente dos bits que difieren.

Lo siguiente es una implementación naive que funciona generando todos los $2^{n}$ subconjuntos posibles, y hallando subconjuntos de tamaño $K$.

int gray_code (int n) {
    return n ^ (n >> 1);
}

int count_bits (int n) {
    int res = 0;
    for (; n; n >>= 1)
        res += n & 1;
    return res;
}

void all_combinations (int n, int k) {
    for (int i = 0; i < (1 << n); i++) {
        int cur = gray_code (i);
        if (count_bits(cur) == k) {
            for (int j = 0; j < n; j++) {
                if (cur & (1 << j))
                    cout << j + 1;
            }
            cout << "\n";
        }
    }
}

Vale la pena mencionar que existe una implementación más eficiente que solo recurre a construir combinaciones válidas y por lo tanto funciona en $O\left(N \cdot \binom{N}{K}\right)$; sin embargo es de naturaleza recursiva y para valores más pequeños de $N$ probablemente tiene una constante mayor que la solución anterior.

La implementación se deriva de la fórmula:

$$G(N, K) = 0G(N-1, K) \cup 1G(N-1, K-1)^\text{R}$$

Esta fórmula se obtiene modificando la ecuación general para determinar el código de Gray, y funciona seleccionando la subsecuencia de elementos apropiados.

Su implementación es la siguiente:

vector<int> ans;

void gen(int n, int k, int idx, bool rev) {
    if (k > n || k < 0)
        return;

    if (!n) {
        for (int i = 0; i < idx; ++i) {
            if (ans[i])
                cout << i + 1;
        }
        cout << "\n";
        return;
    }

    ans[idx] = rev;
    gen(n - 1, k - rev, idx + 1, false);
    ans[idx] = !rev;
    gen(n - 1, k - !rev, idx + 1, true);
}

void all_combinations(int n, int k) {
    ans.resize(n);
    gen(n, k, 0, false);
}