37. Distribución con restricciones

37.1 Introducción

En una distribución básica podemos colocar objetos libremente. En situaciones reales, cada recipiente puede tener una capacidad, una cantidad mínima o condiciones de compatibilidad.

Las restricciones se incorporan al modelo antes de contar. A veces se resuelven transformando las variables; otras veces requieren complemento, inclusión y exclusión o enumeración controlada.

37.2 Restricción de recipiente no vacío

Si n objetos idénticos se distribuyen en m recipientes y ninguno puede quedar vacío, reservamos un objeto para cada recipiente:

Después de entregar un objeto a cada recipiente, se distribuyen los n-m restantes sin límite inferior.

37.3 Capacidad máxima

Si cada recipiente puede recibir como máximo c objetos, las soluciones deben cumplir:

La fórmula simple de estrellas y barras ya no basta directamente porque debemos excluir las distribuciones que superan la capacidad.

37.4 Simulación de distribuciones válidas

Indica objetos idénticos, recipientes, una capacidad máxima y si cada recipiente debe recibir al menos uno.

37.5 Ejemplo de capacidad

Distribuyamos 5 objetos idénticos entre 3 recipientes, con capacidad máxima 3 y permitiendo recipientes vacíos. Las soluciones incluyen:

Se descartan casos como (5,0,0) porque superan la capacidad máxima.

37.6 Transformar límites inferiores

Si cada recipiente debe recibir al menos l objetos, asignamos primero l a cada uno:

El problema se convierte en una distribución con variables no negativas sobre los objetos que quedan.

37.7 Uso del complemento

Para capacidades pequeñas, podemos contar todas las distribuciones sin límite y restar las que tienen al menos un recipiente sobrecargado.

Si varias distribuciones exceden la capacidad en recipientes diferentes, puede ser necesario aplicar inclusión y exclusión.

37.8 Un ejemplo en JavaScript

El siguiente algoritmo enumera cantidades y conserva las que suman n y respetan un límite.

function distribucionesValidas(n, recipientes, capacidad, actual = [], resultados = []) {
  if (recipientes === 1) {
    if (n <= capacidad) resultados.push([...actual, n]);
    return resultados;
  }

  for (let cantidad = 0; cantidad <= Math.min(n, capacidad); cantidad += 1) {
    distribucionesValidas(n - cantidad, recipientes - 1, capacidad, [...actual, cantidad], resultados);
  }
  return resultados;
}

console.log(distribucionesValidas(5, 3, 3));

37.9 Compatibilidad de objetos

Si los objetos son diferentes, una restricción puede indicar que cierto objeto solo puede ir a determinados recipientes.

En este caso, el principio del producto se aplica multiplicando las opciones compatibles de cada objeto, siempre que las decisiones sean independientes.

37.10 Todos los recipientes ocupados y capacidad

Combinar mínimo y máximo produce un rango para cada variable:

Si n es menor que m o mayor que mc, no existe ninguna distribución válida.

37.11 Aplicaciones en informática

• Distribuir carga con límites de capacidad.
• Asignar datos a particiones no vacías.
• Repartir recursos con mínimos y máximos.
• Modelar almacenamiento en bloques limitados.
• Validar configuraciones de servidores.
• Filtrar asignaciones incompatibles.

37.12 Errores frecuentes

• Aplicar estrellas y barras ignorando una capacidad máxima.
• Olvidar reservar objetos para límites mínimos.
• Aceptar soluciones con suma distinta de n.
• No comprobar si n está dentro de [m, mc].
• Confundir la capacidad de un recipiente con la cantidad total.

37.13 Qué debes recordar de este tema

• Las restricciones se expresan como límites sobre las cantidades.
• Los mínimos pueden eliminarse reservando objetos.
• Las capacidades máximas requieren excluir distribuciones sobrecargadas.
• La enumeración sirve para comprobar casos pequeños.
• El complemento y la inclusión y exclusión ayudan con límites superiores.
• Si n está fuera del rango posible, no existe ninguna solución.

37.14 Conclusión

Distribuir con restricciones exige contar soluciones de una ecuación bajo límites y condiciones. Transformar mínimos, controlar máximos y filtrar casos permite construir modelos correctos para problemas de recursos y asignaciones.

En el próximo tema estudiaremos la introducción a la recurrencia en combinatoria, una herramienta para expresar conteos a partir de problemas más pequeños.