34. Permutaciones con restricciones

34.1 Introducción

Una permutación simple cuenta todos los ordenamientos de n elementos diferentes. Cuando aparece una condición, algunos de esos ordenamientos dejan de ser válidos.

Para resolver el problema podemos contar directamente los casos que cumplen la condición, fijar posiciones, agrupar elementos en bloques o restar los casos prohibidos.

34.2 Posición fija

Si un elemento A debe ocupar una posición específica, esa posición deja de ser una elección. Los otros n-1 elementos pueden ordenarse libremente:

Con 5 elementos y A en la primera posición:

34.3 Dos elementos juntos

Si A y B deben estar juntos, podemos tratarlos como un único bloque. Dentro del bloque existen dos órdenes: AB y BA.

34.4 Simulación de ordenamientos restringidos

Elige la cantidad de elementos y una condición. La simulación genera las permutaciones y conserva las que cumplen la restricción.

34.5 Elementos separados

Si A y B no pueden estar juntos, podemos usar complemento:

Para 5 elementos:

34.6 Varios elementos juntos

Si A, B y C deben permanecer juntos, los tratamos como un bloque. El bloque puede ordenarse internamente de 3! formas.

34.7 Un ejemplo en JavaScript

Podemos generar permutaciones y probar si dos elementos son vecinos.

function permutaciones(elementos, actual = [], resultados = []) {
  if (actual.length === elementos.length) {
    resultados.push(actual.join(""));
    return resultados;
  }
  elementos.forEach(elemento => {
    if (!actual.includes(elemento)) {
      permutaciones(elementos, [...actual, elemento], resultados);
    }
  });
  return resultados;
}

const todas = permutaciones(["A", "B", "C", "D"]);
const juntos = todas.filter(cadena =>
  cadena.includes("AB") || cadena.includes("BA")
);
console.log(juntos);

34.8 Posiciones prohibidas

Si un elemento no puede ocupar determinada posición, podemos fijar esa posición con las opciones permitidas y continuar el conteo.

También podemos contar el complemento: todos los ordenamientos menos los que comienzan con A.

34.9 Restricciones de precedencia

Una condición como “A debe aparecer antes que B” divide los ordenamientos en dos grupos simétricos: los que tienen A antes que B y los que tienen B antes que A.

34.10 Restricciones múltiples

Cuando hay varias restricciones, pueden interactuar. Por ejemplo, “A y B juntos” y “C no puede estar primero” exige contar los casos del bloque y luego revisar la posición de C.

En problemas complejos conviene separar casos, utilizar complemento o enumerar solo si el tamaño es pequeño.

34.11 Aplicaciones en informática

• Ordenar tareas con dependencias.
• Generar secuencias que respetan reglas.
• Asignar procesos a posiciones compatibles.
• Analizar configuraciones con elementos adyacentes.
• Construir casos de prueba restringidos.
• Estudiar algoritmos de búsqueda con poda.

34.12 Errores frecuentes

• Usar n! sin eliminar los casos prohibidos.
• Tratar un bloque como un solo elemento y olvidar sus órdenes internos.
• Restar casos de adyacencia sin considerar ambas orientaciones AB y BA.
• Confundir “juntos” con “en posiciones fijas”.
• Contar dos veces casos que cumplen varias restricciones.

34.13 Qué debes recordar de este tema

• Una posición fija reduce el problema a (n-1)!.
• Elementos juntos pueden tratarse como un bloque.
• Elementos separados pueden contarse por complemento.
• Un bloque tiene sus propios ordenamientos internos.
• Las restricciones múltiples requieren evitar superposiciones.
• La enumeración permite verificar casos pequeños.

34.14 Conclusión

Las permutaciones con restricciones se resuelven modificando el conteo de ordenamientos para reflejar posiciones fijas, bloques, separaciones y precedencias. El complemento y la enumeración son herramientas importantes para validar el resultado.

En el próximo tema estudiaremos problemas de distribución de objetos, donde los elementos se asignarán a recipientes o grupos.