33. Combinaciones con restricciones

33.1 Introducción

Una combinación sin repetición selecciona k elementos de un conjunto de n sin considerar el orden. En muchos problemas, sin embargo, no todas las selecciones son válidas.

Las restricciones pueden resolverse reduciendo el conjunto disponible, fijando elementos obligatorios, separando casos o utilizando complemento e inclusión y exclusión.

33.2 Elemento obligatorio

Si un elemento A debe pertenecer a una selección de tamaño k, lo fijamos y elegimos los k-1 elementos restantes entre los otros n-1:

Por ejemplo, equipos de 3 entre 8 personas que deben incluir a Ana:

33.3 Elemento prohibido

Si A no puede pertenecer a la selección, elegimos todos los elementos entre los n-1 restantes:

Para equipos de 3 entre 8 personas que no pueden incluir a Ana:

33.4 Simulación de combinaciones restringidas

Elige el tamaño del conjunto, el tamaño de la selección y una condición. La simulación genera las combinaciones y conserva solo las válidas.

33.5 Dos elementos obligatorios

Si A y B deben aparecer en una selección de tamaño k, ambos quedan fijados y elegimos los k-2 restantes entre n-2 elementos:

Para elegir 4 personas de 10 incluyendo a Ana y Beto:

33.6 Al menos uno de varios elementos

Para contar selecciones que incluyen al menos uno de ciertos elementos, suele ser más sencillo usar complemento:

Si queremos equipos que contengan a Ana o a Beto, contamos todos los equipos y restamos los que no contienen a ninguno de los dos.

33.7 Inclusión y exclusión

Si A representa las selecciones que incluyen a Ana y B las que incluyen a Beto:

La intersección contiene los equipos que incluyen a ambas personas y se resta porque fueron contados dos veces.

33.8 Un ejemplo en JavaScript

Podemos generar combinaciones y comprobar una condición con un filtro.

function combinaciones(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]);
    combinaciones(elementos, k, indice + 1, actual, resultados);
    actual.pop();
  }
  return resultados;
}

const equipos = combinaciones(["A", "B", "C", "D", "E"], 3);
const conA = equipos.filter(equipo => equipo.includes("A"));
console.log(conA);

33.9 Restricciones de incompatibilidad

Si A y B no pueden aparecer juntos, generamos todas las selecciones y eliminamos las que contienen ambos:

El segundo término cuenta las selecciones que contienen simultáneamente los dos elementos incompatibles.

33.10 Restricciones por cantidad

También podemos exigir una cantidad exacta de elementos de una categoría. Por ejemplo, un equipo puede necesitar exactamente 2 personas de un grupo A y 1 de un grupo B:

El producto aparece porque las selecciones de los dos grupos se realizan en etapas independientes.

33.11 Aplicaciones en informática

• Seleccionar equipos con integrantes obligatorios.
• Elegir características compatibles.
• Formar grupos excluyendo combinaciones prohibidas.
• Asignar recursos respetando categorías.
• Filtrar subconjuntos que cumplen reglas.
• Construir casos de prueba con condiciones exactas.

33.12 Errores frecuentes

• Fijar un elemento obligatorio y olvidarse de reducir k.
• Excluir un elemento sin reducir n.
• Restar dos veces las selecciones que contienen dos elementos obligatorios.
• Confundir “al menos uno” con “exactamente uno”.
• Ignorar incompatibilidades entre elementos.

33.13 Qué debes recordar de este tema

• Un elemento obligatorio puede fijarse y reducir el problema.
• Un elemento prohibido se elimina del conjunto disponible.
• Dos elementos obligatorios reducen n y k en dos unidades.
• El complemento cuenta selecciones que no contienen elementos requeridos.
• La inclusión y exclusión corrige superposiciones.
• Las restricciones por categorías suelen combinar productos y combinaciones.

33.14 Conclusión

Las combinaciones con restricciones se resuelven identificando qué elementos deben incluirse, cuáles deben excluirse y qué casos se superponen. Fijar elementos, usar complemento y aplicar inclusión y exclusión son estrategias fundamentales.

En el próximo tema estudiaremos las permutaciones con restricciones, donde las condiciones afectan el orden de los elementos.