30. Conteo de subconjuntos

30.1 Introducción

Un subconjunto se forma eligiendo algunos elementos de un conjunto original. Puede contener todos los elementos, ninguno o cualquier cantidad intermedia.

Contar subconjuntos es una aplicación central de la combinatoria porque aparece en selección de características, agrupación de datos, búsqueda y análisis de configuraciones.

30.2 Dos decisiones por elemento

Para cada elemento existen dos opciones independientes:

• Incluirlo en el subconjunto.
• Excluirlo del subconjunto.

Si el conjunto tiene n elementos, el principio del producto produce:

30.3 El conjunto vacío y el conjunto completo

Entre todos los subconjuntos siempre aparecen dos casos especiales:

Hay exactamente un subconjunto vacío y exactamente un subconjunto que contiene todos los elementos.

30.4 Simulación de subconjuntos

Escribe un conjunto pequeño y elige si quieres mostrar todos sus subconjuntos o solo los de un tamaño determinado.

30.5 Subconjuntos de tamaño fijo

Si queremos contar solamente los subconjuntos de tamaño k, utilizamos un coeficiente binomial:

Por ejemplo, un conjunto de 5 elementos tiene:

30.6 Relación entre ambos conteos

Todos los subconjuntos se agrupan según su tamaño. Por eso:

El lado derecho suma los subconjuntos de cada tamaño y el lado izquierdo cuenta directamente las dos decisiones de cada elemento.

30.7 Un ejemplo en JavaScript

Podemos representar cada subconjunto mediante una máscara de inclusión: cada posición indica si un elemento se incluye o no.

function subconjuntos(elementos) {
  const resultados = [];
  const cantidad = 2 ** elementos.length;

  for (let mascara = 0; mascara < cantidad; mascara += 1) {
    const subconjunto = [];
    elementos.forEach((elemento, indice) => {
      if (mascara & (1 << indice)) subconjunto.push(elemento);
    });
    resultados.push(subconjunto);
  }
  return resultados;
}

console.log(subconjuntos(["A", "B", "C"]));

Con 3 elementos, las máscaras van de 0 a 7 y se generan 2³ = 8 subconjuntos.

30.8 Generar subconjuntos de tamaño k

Para generar solo subconjuntos de un tamaño determinado, podemos utilizar una construcción recursiva que elige o descarta elementos hasta completar k.

function deTamañoK(elementos, k, inicio = 0, actual = [], resultados = []) {
  if (actual.length === k) {
    resultados.push([...actual]);
    return resultados;
  }
  for (let indice = inicio; indice < elementos.length; indice += 1) {
    actual.push(elementos[indice]);
    deTamañoK(elementos, k, indice + 1, actual, resultados);
    actual.pop();
  }
  return resultados;
}

console.log(deTamañoK(["A", "B", "C", "D"], 2));

30.9 Restricciones sobre subconjuntos

Podemos exigir que un subconjunto incluya un elemento, excluya otro o tenga un tamaño específico.

Las dos cantidades son iguales por simetría: cada subconjunto que contiene A corresponde a uno que no lo contiene al quitar o agregar A.

30.10 Subconjuntos y búsqueda

Un algoritmo que prueba todos los subconjuntos puede tener un espacio de búsqueda de tamaño 2ⁿ. Este crecimiento puede ser manejable para n pequeño, pero rápidamente se vuelve grande.

El conteo combinatorio permite estimar el costo antes de ejecutar la búsqueda.

30.11 Aplicaciones en informática

• Seleccionar subconjuntos de características.
• Resolver problemas de selección y optimización.
• Representar permisos habilitados o deshabilitados.
• Generar configuraciones de pruebas.
• Analizar combinaciones de recursos.
• Estimar el tamaño de búsquedas exhaustivas.

30.12 Errores frecuentes

• Olvidar incluir el subconjunto vacío.
• Contar el conjunto original como un caso diferente cuando corresponde incluirlo.
• Confundir 2ⁿ con n².
• Generar dos veces el mismo subconjunto en distinto orden.
• Usar C(n,k) cuando se quieren todos los tamaños.

30.13 Qué debes recordar de este tema

• Cada elemento tiene dos decisiones: incluirlo o excluirlo.
• Un conjunto de n elementos tiene 2ⁿ subconjuntos.
• Los subconjuntos de tamaño k se cuentan con C(n,k).
• La suma de todos los coeficientes binomiales es 2ⁿ.
• El subconjunto vacío y el conjunto completo siempre están incluidos.
• Enumerar subconjuntos puede producir un espacio de búsqueda exponencial.

30.14 Conclusión

Contar subconjuntos consiste en reconocer que cada elemento puede incluirse o excluirse. Esta decisión binaria produce 2ⁿ posibilidades, mientras que fijar el tamaño de la selección conduce a los coeficientes binomiales.

En el próximo tema estudiaremos el conteo de particiones, donde los elementos se agrupan en partes o bloques.