28. Conteo de posiciones y asignaciones

28.1 Introducción

Muchos problemas informáticos consisten en asignar objetos a lugares: tareas a turnos, personas a cargos, recursos a servidores o valores a campos.

La pregunta clave es si las posiciones tienen identidad. Si cambiar los elementos de lugar produce una asignación diferente, el orden importa y debemos contar las posiciones una por una.

28.2 Posiciones diferenciadas

Una posición es diferenciada cuando tiene un nombre o función propia. Por ejemplo, presidente, secretario y tesorero son posiciones distintas.

Cuando las posiciones son distintas, una asignación es una secuencia ordenada de elementos.

28.3 Asignación sin repetición

Si hay n elementos y k posiciones, y cada elemento puede ocupar como máximo una posición, la cantidad de asignaciones es:

La primera posición tiene n opciones, la segunda n-1 y así sucesivamente.

28.4 Ejemplo de cargos

De 8 personas se deben asignar 3 cargos diferentes:

La asignación de una persona a un cargo reduce las opciones para los cargos siguientes porque no se permite repetir personas.

28.5 Simulación de asignaciones

Selecciona la cantidad de elementos y posiciones. La simulación genera asignaciones sin repetir y muestra el total calculado.

28.6 Asignación con repetición

Si un elemento puede ocupar varias posiciones, cada posición mantiene las mismas n opciones. La cantidad es:

Por ejemplo, asignar uno de 4 estados a cada uno de 3 campos permite 4³ = 64 configuraciones si los estados pueden repetirse.

28.7 Un ejemplo en JavaScript

La función genera asignaciones a posiciones diferenciadas sin reutilizar el elemento seleccionado.

function asignar(elementos, posiciones, inicio = 0, actual = [], resultados = []) {
  if (actual.length === posiciones) {
    resultados.push([...actual]);
    return resultados;
  }

  elementos.forEach((elemento, indice) => {
    if (actual.includes(elemento)) return;
    asignar(elementos, posiciones, indice + 1, [...actual, elemento], resultados);
  });
  return resultados;
}

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

En este ejemplo, el parámetro inicio no se necesita para recorrer combinaciones; las posiciones pueden recibir cualquier elemento que todavía no haya sido utilizado.

28.8 Asignaciones y combinaciones

Si primero elegimos k elementos de un conjunto de n y luego los asignamos a k posiciones, podemos separar el conteo en dos etapas:

La primera etapa selecciona el grupo y la segunda decide qué elemento ocupa cada posición.

28.9 Restricciones de compatibilidad

En una asignación real, no todos los elementos pueden ocupar todas las posiciones. Puede haber capacidades, permisos o incompatibilidades.

Si las opciones dependen de decisiones anteriores, conviene usar un árbol de casos, separar situaciones o generar solo asignaciones válidas.

28.10 Asignación a posiciones idénticas

Si las posiciones no se distinguen, cambiar dos elementos de lugar no produce una asignación nueva. En ese caso el problema se parece a una combinación o a una distribución de objetos.

28.11 Aplicaciones en informática

• Asignar tareas a turnos o prioridades.
• Distribuir recursos entre servidores.
• Colocar valores en posiciones de una estructura.
• Asignar usuarios a roles diferentes.
• Generar configuraciones de parámetros.
• Analizar espacios de asignaciones compatibles.

28.12 Errores frecuentes

• Tratar posiciones diferenciadas como si fueran idénticas.
• Permitir que un elemento se use dos veces sin autorización.
• Usar n! cuando solo hay k posiciones.
• Ignorar incompatibilidades entre elementos y posiciones.
• Contar primero una selección y olvidar ordenar sus elementos.

28.13 Qué debes recordar de este tema

• Las posiciones diferenciadas hacen que el orden importe.
• Sin repetición, la cantidad es V(n,k).
• Con repetición permitida, la cantidad básica es n^k.
• Elegir y luego ordenar equivale a multiplicar C(n,k) por k!.
• Las restricciones de compatibilidad pueden reducir las opciones por etapa.
• Si las posiciones son idénticas, el modelo cambia.

28.14 Conclusión

Contar posiciones y asignaciones requiere determinar si cada lugar tiene una identidad y si los elementos pueden repetirse. Una vez definido el modelo, las variaciones, combinaciones y principios de conteo permiten calcular las asignaciones posibles.

En el próximo tema estudiaremos el conteo de cadenas y secuencias, donde las posiciones representan lugares dentro de una sucesión.