13. Permutaciones circulares

13.1 Introducción

En una fila, cambiar todos los elementos una posición produce un ordenamiento diferente. En un círculo, en cambio, una rotación completa puede dejar las relaciones entre vecinos exactamente iguales.

Por eso, al contar personas alrededor de una mesa o elementos en una disposición circular, debemos decidir si las rotaciones representan configuraciones nuevas o la misma configuración.

13.2 Diferencia entre una fila y un círculo

Con cuatro elementos A, B, C y D, en una fila hay:

En un círculo, estas disposiciones representan el mismo arreglo por rotación:

Las cuatro secuencias tienen los mismos vecinos. Por eso cada arreglo circular fue contado 4 veces en el cálculo lineal.

13.3 Fórmula de las permutaciones circulares

Para n elementos diferentes alrededor de un círculo, si las rotaciones se consideran equivalentes, la cantidad de arreglos es:

La fórmula se obtiene fijando un elemento en una posición de referencia y ordenando libremente los otros n - 1 elementos.

13.4 Por qué se fija un elemento

Elegimos un elemento como referencia, por ejemplo A. Esto elimina las diferencias producidas únicamente por rotar todo el círculo.

Fijar A no elimina una relación real entre los elementos. Solo evita contar varias veces el mismo círculo desde distintos puntos de inicio.

13.5 Ejemplo con cuatro elementos

Para A, B, C y D alrededor de un círculo:

Fijamos A y ordenamos B, C y D. Las seis disposiciones relativas son:

13.6 Simulación de arreglos circulares

Escribe entre 3 y 5 elementos diferentes. La simulación fija el primer elemento y muestra los arreglos restantes, evitando duplicados por rotación.

13.7 Un ejemplo en JavaScript

Para generar arreglos circulares, fijamos el primer elemento y permutamos los restantes.

function permutar(elementos) {
  if (elementos.length === 0) return [[]];
  const resultados = [];

  elementos.forEach((elemento, indice) => {
    const restantes = elementos.filter((_, posicion) => posicion !== indice);
    permutar(restantes).forEach(resto => {
      resultados.push([elemento, ...resto]);
    });
  });
  return resultados;
}

const elementos = ["A", "B", "C", "D"];
const circulares = permutar(elementos.slice(1))
  .map(resto => [elementos[0], ...resto]);

console.log(circulares.map(arreglo => arreglo.join("-")));

El primer elemento permanece siempre en la primera posición de la representación lineal. Cada lista restante representa un círculo diferente.

13.8 Rotaciones equivalentes

Si un arreglo circular comienza en otro elemento, no necesariamente se trata de una configuración nueva. Por ejemplo:

Para comprobar si dos arreglos son iguales por rotación, podemos buscar si uno aparece dentro de la repetición circular del otro.

function sonRotacionesIguales(a, b) {
  if (a.length !== b.length) return false;
  const doble = [...a, ...a];
  return doble.slice(0, -1).some((_, inicio) =>
    doble.slice(inicio, inicio + b.length).every((valor, indice) => valor === b[indice])
  );
}

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

13.9 Cuando el sentido importa

En algunos problemas, leer el círculo en sentido horario o antihorario produce configuraciones diferentes. En otros, un arreglo y su reflejo se consideran iguales.

Siempre debemos leer con cuidado qué transformaciones consideran equivalente las condiciones del problema.

13.10 Restricciones en círculos

Si dos elementos deben quedar juntos, pueden tratarse temporalmente como un bloque. Si dos personas no pueden ser vecinas, es posible contar todos los arreglos y restar los que incumplen la condición.

Estas técnicas combinan permutaciones circulares con principios de conteo y se desarrollarán en temas posteriores.

13.11 Aplicaciones en informática

• Organizar elementos en ciclos o estructuras circulares.
• Analizar recorridos que regresan al punto de partida.
• Contar configuraciones de turnos y rotaciones.
• Modelar anillos, ciclos y secuencias periódicas.
• Eliminar duplicados causados por distintos puntos de inicio.
• Generar configuraciones circulares para pruebas o simulaciones.

13.12 Errores frecuentes

• Usar n! sin considerar que las rotaciones son equivalentes.
• Dividir por n cuando en realidad las posiciones de referencia ya están fijadas.
• Confundir rotación con reflexión.
• Contar como diferentes dos arreglos que solo cambiaron el punto de inicio.
• Aplicar (n - 1)! cuando el problema considera posiciones circulares distinguidas.

13.13 Qué debes recordar de este tema

• En una permutación circular, las rotaciones suelen considerarse equivalentes.
• Se fija un elemento para eliminar el conteo repetido por rotación.
• Para n elementos diferentes, el conteo habitual es (n - 1)!.
• El tratamiento de los reflejos depende del contexto.
• Las restricciones pueden resolverse mediante bloques, casos o complemento.
• La simulación debe fijar una referencia para no mostrar duplicados.

13.14 Conclusión

Las permutaciones circulares adaptan el conteo de ordenamientos al hecho de que no existe una primera posición natural. Fijar un elemento elimina las rotaciones equivalentes y deja (n - 1)! arreglos para los elementos restantes.

En el próximo tema estudiaremos las variaciones sin repetición, donde se ordena solo una parte de los elementos disponibles.