Algoritmo de Steinhaus–Johnson–Trotter

El algoritmo Steinhaus–Johnson–Trotter o algoritmo Johnson–Trotter, también llamado cambios simples, es un algoritmo que lleva el nombre de Hugo Steinhaus, Selmer M. Johnson y Hale F. Trotter que genera todas las permutaciones de n elementos. Cada permutación en la secuencia que genera difiere de la permutación anterior al intercambiar dos elementos adyacentes de la secuencia. De manera equivalente, este algoritmo encuentra un ciclo hamiltoniano en el permutoedro. El algoritmo Johnson-Trotter ofrece una forma eficaz de generar directamente permutaciones de la longitud requerida sin calcular permutaciones más cortas.​

Historia

Johnson y Trotter descubrieron el algoritmo independientemente el uno del otro a principios de la década de 1960. Un libro de Steinhaus, publicado originalmente en 1958 y traducido al inglés en 1963, describe un rompecabezas relacionado de generar todas las permutaciones mediante un sistema de partículas, cada una moviéndose a una velocidad constante a lo largo de una línea e intercambiando posiciones cuando una partícula adelanta a otra. No hay solución posible para n>3, porque el número de intercambios es mucho menor que el número de permutaciones, pero el algoritmo Steinhaus–Johnson–Trotter describe el movimiento de partículas con velocidades no constantes que generan todas las permutaciones.

Fuera de las matemáticas, el mismo método se conoció durante mucho más tiempo como un método para cambiar el sonido de las campanas de la iglesia: proporciona un procedimiento mediante el cual se puede tocar un conjunto de campanas a través de todas las permutaciones posibles, cambiando el orden de solo dos campanas por cambio. Estos llamados "cambios simples" se registraron ya en 1621 para cuatro campanas, y un libro de 1677 de Fabian Stedman enumera las soluciones para hasta seis campanas. Más recientemente, los timbres de cambio han cumplido con la regla de que ninguna campana puede permanecer en la misma posición durante tres permutaciones consecutivas; esta regla es no sirve para los cambios simples, por lo que se han ideado otras estrategias que intercambian múltiples campanas por cambio.​

¿Cómo funciona el algoritmo?

El algoritmo Johnson-Trotter es un algoritmo para calcular permutaciones dado un conjunto de valores. Una permutación es una forma de alterar los valores en un conjunto para crear una secuencia única diferente de la original. Si tenemos el conjunto {1, 2, 3, 4, 5} una permutación sería 2,1,4,5,3 y otra sería 3,4,2,1,5. Usando un peculiar pequeño algoritmo, podemos transponer valores en el conjunto para obtener todas las permutaciones de ese conjunto dado. Podría usar un algoritmo de este tipo para encontrar una palabra que podría estar codificada u obtener una secuencia única dado que el conjunto contiene suficientes valores. 

Existen muchos algoritmos para encontrar permutaciones. El de Steinhaus–Johnson–Trotter es solo uno de muchos, y como todos los algoritmos, tiene sus limitaciones. Pero aunque la comprensión del mismo no es exactamente difícil, contiene algunas reglas que debemos seguir. Cada valor en nuestro conjunto de números recibe una dirección de movilidad. Esto significa que a medida que intercambiamos el valor también tiene una dirección en la que se intercambia.

1) Puede intercambiar con el vecino a la izquierda o derecha inmediata (determinado por su movilidad). Ahora bien, si un valor está en el extremo izquierdo y tiene movilidad hacia la izquierda, se considera inmóvil. Lo mismo con si está en el extremo derecho y tiene derecho a la movilidad. Para empezar, todos los valores han dejado movilidad. 2) El intercambio solo tendrá lugar si el vecino al lado (en la dirección de su movilidad) es menor que el valor que se intercambia. De lo contrario, también se considera bloqueado. Por ejemplo, si 3 y 2 están uno al lado del otro y ambos se mueven hacia la izquierda, no se realiza ningún intercambio hacia la izquierda porque 3 es mayor que 2. Actualmente, 2 está bloqueado en su lugar. Pero si hubiese sido 1 y 4, entonces 4 se intercambiará. 3) Se realiza un intercambio en cada pase. Todos los valores en el conjunto que son de un valor más alto que el valor intercambiado tendrán su dirección de movilidad cambiada a la otra dirección.

En resumen, lo que este algoritmo hace es buscar el valor móvil más alto en el conjunto, luego lo intercambia en la dirección de su movilidad. Si el valor más alto se considera bloqueado, buscará el segundo, tercer y cuarto número más alto y así sucesivamente hasta que no haya más números. Entonces, lo que necesitamos hacer es una forma de 1) encontrar el número móvil más alto actualmente, 2) una rutina para intercambiar los valores en el conjunto y 3) un bucle principal que imprimirá cada uno permutación y continuar hasta que se agoten todas las permutaciones.​​

La complejidad de este algoritmo, usando montículos de Fibonacci en la implementación del algoritmo de Dijkstra, es de O(V²log V + VE): el algoritmo usa un tiempo de O(VE) para la fase Bellman-Ford del algoritmo, y O(V log V + E) para cada una de las V instancias realizadas del algoritmo de Dijkstra. Entonces, cuando el grafo es disperso el tiempo total del algoritmo puede ser menor que el algoritmo de Floyd-Warshall, que resuelve el mismo problema en un tiempo de O(V³).

Aceleración de Even

Una mejora posterior de Shimon Even proporciona una mejora en el tiempo de ejecución al almacenar información adicional para cada elemento en la permutación: su posición y una dirección (positiva, negativa o cero) en la que se está moviendo actualmente (esencialmente, esta es la misma información calculada utilizando la paridad de la permutación en la versión del algoritmo de Johnson). Inicialmente, la dirección del número 1 es cero, y todos los demás elementos tienen una dirección negativa:

1 −2 −3

En cada paso, el algoritmo encuentra el elemento más grande con una dirección distinta de cero y lo intercambia en la dirección indicada:

1 −3 −2

Si esto hace que el elemento elegido alcance la primera o la última posición dentro de la permutación, o si el siguiente elemento en la misma dirección es mayor que el elemento elegido, la dirección del elemento elegido se establece en cero:

3 1 −2

Después de cada paso, todos los elementos mayores que el elemento elegido (que anteriormente tenía la dirección cero) tienen sus direcciones establecidas para indicar el movimiento hacia el elemento elegido. Es decir, positivo para todos los elementos entre el inicio de la permutación y el elemento elegido, y negativo para los elementos hacia el final. Por lo tanto, en este ejemplo, después de que el número 2 se mueve, el número 3 se vuelve a marcar con una dirección:

+3 2 1

Los dos pasos restantes del algoritmo para n=3 son:

2 +3 1 2 1 3

Cuando todos los números quedan sin marcar, el algoritmo termina. Este algoritmo toma tiempo O(i) para cada paso en el que el mayor número para moverse es n-i+1. Por lo tanto, los intercambios que involucran el número n toman solo tiempo constante; Dado que estos intercambios representan todos menos una fracción de 1/n de todos los intercambios realizados por el algoritmo, el tiempo promedio por permutación generada también es constante, aunque un pequeño número de permutaciones llevará una mayor cantidad de tiempo.  Una versión sin bucle más compleja del mismo procedimiento permite que se realice en tiempo constante por permutación en todos los casos; sin embargo, las modificaciones necesarias para eliminar los bucles del procedimiento lo hacen más lento en la práctica.​

Interpretación geométrica

El conjunto de todas las permutaciones de n elementos puede representarse geométricamente mediante un permutoedro, el politopo formado a partir del casco convexo de n! vectores, las permutaciones del vector (1,2, ... n). Aunque se define en el espacio n-dimensional, en realidad es un  politopo (n-1)-dimensional. Por ejemplo, el permutoedro en cuatro elementos es un poliedro tridimensional, el octaedro truncado. Si cada vértice del permutoedro está marcado por la permutación inversa a la permutación definida por sus coordenadas de vértice, el etiquetado resultante describe un gráfico de Cayley del grupo simétrico de permutaciones en n elementos, según lo generado por las permutaciones que intercambian pares de elementos adyacentes. Por lo tanto, cada dos permutaciones consecutivas en la secuencia generada por el algoritmo Steinhaus–Johnson–Trotter corresponden de esta manera a dos vértices que forman los puntos finales de un borde en el permutoedro, y toda la secuencia de permutaciones describe un camino hamiltoniano en el permutoedro, un camino que pasa a través de cada vértice exactamente una vez. Si la secuencia de permutaciones se completa agregando una arista más desde la última permutación a la primera en la secuencia, el resultado es un ciclo hamiltoniano.

Relación con los códigos de Gray

Un código Gray para números en una raíz dada es una secuencia que contiene cada número hasta un límite dado exactamente una vez, de tal manera que cada par de números consecutivos difiere en uno en un solo dígito. El n! las permutaciones de los n números del 1 al n se pueden colocar en correspondencia uno a uno con el n! números del 0 al n!-1 emparejando cada permutación con la secuencia de números c_i que cuentan el número de posiciones en la permutación que están a la derecha del valor i y que contienen un valor menor que i (es decir, el número de inversiones para el que i es el mayor de los dos valores invertidos), y luego interpretar estas secuencias como números en el sistema de números factoriales, es decir, el sistema de radix mixto con secuencia de radix (1,2,3,4). Por ejemplo, la permutación (3,1,4,5,2) daría los valores c₁= 0, c₂=0, c₃=2, c₄=1 y c₅=1. La secuencia de estos valores, (0,0,2,1,1), da el número 0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

Las permutaciones consecutivas en la secuencia generada por el algoritmo Steinhaus–Johnson–Trotter tienen un número de inversiones que difieren en uno, formando un código Gray para el sistema de números factoriales.

En términos más generales, los investigadores de algoritmos combinatorios han establecido un código Gray para un conjunto de objetos combinatorios para que sea un orden de los objetos en los que cada dos objetos consecutivos difieren de la manera mínima posible.​

El algoritmo en diferentes lenguajes de programación

JAVA​

public class JohnsonTrotter {
   public static void perm(int n) {
       int[] p   = new int[n];     // permutation
       int[] pi  = new int[n];     // inverse permutation
       int[] dir = new int[n];     // direction = +1 or -1
       for (int i = 0; i < n; i++) {
           dir[i] = -1;
           p[i]  = i;
           pi[i] = i;
       }
       perm(0, p, pi, dir);
       StdOut.printf("   (0 1)\n");
   }
 
 public static void perm(int n, int[] p, int[] pi, int[] dir) { 
       // base case - print out permutation
       if (n >= p.length) {
           for (int i = 0; i < p.length; i++)
               StdOut.print(p[i]);
           return;
       }
      
      perm(n+1, p, pi, dir);
       for (int i = 0; i <= n-1; i++) {
           // swap 
           StdOut.printf("   (%d %d)\n", pi[n], pi[n] + dir[n]);
           int z = p[pi[n] + dir[n];
           p[pi[n]] = z;
           p[pi[n] + dir[n]] = n;
           pi[z] = pi[n];
           pi[n] = pi[n] + dir[n];  
           perm(n+1, p, pi, dir); 
       }
       dir[n] = -dir[n];
   }
  
  public static void main(String[] args) {
       int n = Integer.parseInt(args[0]);
       perm(n);
   }
}

C++​

#include <cstdlib>
using namespace std;

struct Arista{
   unsigned o;
   unsigned d;
   int peso;
   LAristas sig;
};

typedef LAristas Arista*;
typedef TGrafo LArista[N];
typedef TVector int[N];
typedef TMatriz TVector[N];

void johnson(const TGrafo &grafo, int ig, TMatriz &distancias, TMatriz &previos){
   Arista* p;
   TVector min_caminos;
   TVector aux_dist;
   TVector aux_prev;
   grafo[ig] = nueva_arista(ig,1,0,NULL);
   ig++;
   p = grafo[ig];
   for(unsigned i=2; i<=ig-2; i++){
       p->sig = nueva_arista(ig,i,0,NULL);
       p = p->sig;
   }
   
   BellmanFord(grafo,ig, min_caminos);
   for(unsigned i=1; i<=ig-1; i++){
       p = grafo[i];
       while(p != NULL){
           p->peso = p->peso + min_caminos[p->o] - min_caminos[p->d];
           p = p->sig;
       }
   }
   
   for(unsigned i=1; i<=ig-2; i++){
           Dijkstra(grafo,i-1, aux_dist,aux_prev)                                         
           previos[i-1] = aux_prev;
           CalcularDistancias(grafo, previos, aux_dist,distancias);
   }
}

PYTHON​

def nobody():
   while True:
       yield False
# The term "troll" is taken from Knuth's choice of word

def sjt(pi, inv, i, trolls):
   d = -1  # Directoin. -1 is descending, +1 is ascending.
   while True:
       j = inv[i]  # j is the position of the current "troll"
       if pi[j] < pi[j + d]:
           d = -d
           yield next(trolls[i - 1])
       else:
           pi[j], pi[j + d] = pi[j + d], pi[j]
           inv[i] += d
           inv[pi[j]] -= d
           yield True
           
def setup(n):
   # Pad pi with n + 2, so that pi[i] will always be < the two ends.
   pi = [n + 2] + [i for i in range(1, n + 1)] + [n + 2]
   inv = pi[:-1]
   # nobody simply continuously yields False. By adding a "nobody" generator
   # at both ends of trolls, False is autmatically yieded by sjt when needed.
   trolls = [nobody()]
   trolls.extend(sjt(pi, inv, i + 1, trolls) for i in range(n))
   trolls += [nobody()]
   # The lead troll will be the item n in the permutation
   lead_troll = trolls[-2]
   return pi, lead_troll
def permutations(n):

   pi, lead_troll = setup(n)
   yield pi[1:-1]
   while next(lead_troll):
       yield pi[1:-1]
def cyclic_test(n):

   pi, lead_troll = setup(n)
   c = 0
   while True:
       print('Output: ', .join(str(x) for x in pi[1:-1]))
       c += 1
       if not next(lead_troll):
           print('-------')
           print(c)
           print('-------')
           sleep(1)
           c = 0
           
if __name__ == '__main__':
   print('\n'.join(.join(str(x) for x in pi) for pi in permutations(1)))
   print('\n'.join(.join(str(x) for x in pi) for pi in permutations(2)))
   print('\n'.join(.join(str(x) for x in pi) for pi in permutations(3)))
   print('\n'.join(.join(str(x) for x in pi) for pi in permutations(4)))
   cyclic_test(3)

Véase también

• Algoritmo de Heap
• Algoritmo de Fisher-Yates

Referencias

• Datos: Q4925248