35. Problemas de distribución de objetos

Distribuir objetos consiste en asignarlos a recipientes, grupos o categorías, analizando si los objetos y los recipientes son distinguibles y qué restricciones existen.

35.1 Introducción

Muchos problemas combinatorios pueden describirse como una distribución: colocar tareas en servidores, repartir recursos entre grupos, asignar archivos a carpetas o ubicar objetos en recipientes.

Antes de contar hay que identificar el modelo. No es lo mismo distribuir objetos diferentes que distribuir objetos idénticos, ni usar recipientes etiquetados que recipientes indistinguibles.

35.2 Preguntas para definir el modelo

  • ¿Los objetos se pueden distinguir entre sí?
  • ¿Los recipientes o grupos tienen etiquetas?
  • ¿Se permite que un recipiente quede vacío?
  • ¿Cada objeto debe ir a un único recipiente?
  • ¿Existen límites de capacidad?
  • ¿El orden dentro de un recipiente importa?

Las respuestas determinan si aplicaremos producto, combinaciones, particiones o técnicas de distribución.

35.3 Objetos diferentes y recipientes etiquetados

Si hay n objetos diferentes y m recipientes identificados, cada objeto tiene m opciones independientes.

Total = mn

Por ejemplo, 4 archivos diferentes distribuidos entre 3 carpetas etiquetadas producen:

34 = 81 asignaciones

35.4 Simulación de distribución

Indica la cantidad de objetos y recipientes etiquetados. La simulación muestra las asignaciones posibles en casos pequeños.

Asignador de objetos a recipientes

35.5 Recipientes vacíos permitidos

La fórmula mn permite que algunos recipientes queden vacíos. Cada objeto elige un recipiente, sin exigir que todos reciban al menos uno.

3 objetos, 2 recipientes:
A → 1, B → 1, C → 1 es válido
También puede quedar el recipiente 2 vacío

35.6 Recipientes no vacíos

Si todos los recipientes deben recibir al menos un objeto, no podemos aplicar directamente mn. Debemos eliminar las asignaciones que dejan recipientes vacíos o utilizar números de Stirling y combinaciones.

Objetos diferentes en m recipientes no vacíos
= S(n,m) × m!

S(n,m) forma grupos no etiquetados y m! asigna etiquetas a esos grupos.

35.7 Un ejemplo en JavaScript

Si los recipientes están etiquetados y pueden quedar vacíos, la cantidad se calcula con una potencia.

function contarDistribuciones(objetos, recipientes) {
  return recipientes ** objetos;
}

console.log(contarDistribuciones(4, 3));
console.log('Cada objeto elige uno de los recipientes.');

35.8 Distribuir sin repetir posiciones

Si cada recipiente puede recibir como máximo un objeto y hay n objetos para m posiciones, el problema se convierte en una asignación parcial:

V(n, m) = n! / (n - m)!
cuando m ≤ n

Aquí un objeto no puede compartir recipiente con otro, por lo que el número de opciones disminuye.

35.9 Capacidad de los recipientes

Las capacidades agregan restricciones. Si un recipiente solo puede recibir cierta cantidad, debemos descartar asignaciones que superen ese límite.

Sin capacidad: mn
Con capacidad: contar solo distribuciones admisibles

Para pocos objetos podemos enumerar y filtrar. Para problemas grandes se utilizan combinaciones, recurrencias o métodos de distribución.

35.10 Recipientes etiquetados y no etiquetados

Modelo¿Se distinguen objetos?¿Se distinguen recipientes?Ejemplo
Asignación básicaSíSíArchivos diferentes a carpetas con nombre.
Distribución de idénticosNoSíUnidades iguales entre cajas numeradas.
ParticiónSíNoPersonas separadas en grupos sin nombre.

35.11 Aplicaciones en informática

  • Asignar archivos a directorios.
  • Distribuir tareas entre servidores.
  • Repartir datos entre particiones.
  • Asignar usuarios a grupos o permisos.
  • Distribuir recursos de memoria o almacenamiento.
  • Analizar configuraciones de carga y balanceo.

35.12 Errores frecuentes

  • Confundir objetos diferentes con objetos idénticos.
  • Olvidar si los recipientes tienen etiquetas.
  • Usar mn cuando todos los recipientes deben estar ocupados.
  • Ignorar capacidades máximas.
  • Contar como diferentes distribuciones que solo cambian recipientes indistinguibles.

35.13 Qué debes recordar de este tema

  • Distribuir objetos equivale a asignarlos a recipientes o categorías.
  • Con objetos diferentes y recipientes etiquetados, el modelo básico es mn.
  • La fórmula permite recipientes vacíos salvo que se indique lo contrario.
  • Las capacidades y ocupación obligatoria agregan restricciones.
  • Los recipientes no etiquetados conducen a particiones.
  • Definir el modelo es el paso más importante del conteo.

35.14 Conclusión

Los problemas de distribución se resuelven identificando qué se distribuye, dónde se coloca y qué restricciones existen. El caso básico de objetos diferentes y recipientes etiquetados se obtiene mediante el principio del producto.

En el próximo tema estudiaremos por separado la distribución de objetos idénticos y diferentes.

Volver al índice