Algoritmo: cómo encontrar la próxima permutación lexicográfica

Si describe brevemente cuál es el orden lexicográfico, esto se ordena en orden alfabético. Es decir la secuencia de caracteres - AAA → AAB → AAC → AAD → ……… → WWW - se ordena en orden alfabético (o en nuestro caso lexicográfico).

Imagine que tiene una secuencia finita de caracteres, por ejemplo, 0, 1, 2, 5, 3, 3, 0 y necesita encontrar todas las permutaciones posibles de estos caracteres. El más intuitivo, pero también el más difícil, es el algoritmo recursivo, cuando seleccionamos el primer carácter de la secuencia, luego seleccionamos el segundo, el tercero, etc., recursivamente, hasta que se seleccionan todos los caracteres de la secuencia. Está claro que la complejidad de tal algoritmo es O (n!).

Pero resulta que el algoritmo más simple para generar todas las permutaciones en orden lexicográfico es comenzar con el más pequeño y calcular repetidamente la próxima permutación en su lugar. Veamos como hacerlo.

Al igual que al calcular el siguiente valor entero, deberíamos intentar aumentar el lado derecho de la secuencia y dejar el lado izquierdo sin cambios.

Como ejemplo, tome la secuencia anterior - (0, 1, 2, 5, 3, 3, 0). Para obtener la secuencia más alta que la original, es suficiente reorganizar el primer y el segundo elemento, pero esto no es necesario, ya que puede reorganizar el segundo y el tercer elemento y obtener una secuencia más cercana en orden ascendente. lo que nos llevará a la próxima permutación más cercana, etc.

El algoritmo más óptimo en este caso sería el siguiente:

1. En primer lugar, debe encontrar el sufijo no creciente más grande. En el ejemplo anterior, esto sería - (5, 3, 3, 0). Si intenta realizar una permutación en esta secuencia, entonces no será más alta que la original.
   Vale la pena decir que puede encontrar esta secuencia en O (n) mirando la secuencia de izquierda a derecha.
2. El siguiente elemento del sufijo es el punto de pivote. En nuestro caso, este es 2. El punto de pivote siempre será menor que el primer elemento del sufijo. Esto significa que en el sufijo ciertamente habrá un elemento que exceda el punto de pivote y si cambiamos el punto de pivote al elemento más pequeño del sufijo que excede el elemento de soporte del punto de pivote, obtendremos una secuencia que exceda el original, en nuestro caso será (0, 1, 3, 5 , 3, 2, 0).
   Es decir El resultado de esta operación será el prefijo ascendente mínimo posible.
   
3. Y en el último paso, debemos ordenar el sufijo en orden ascendente. Es decir obtenemos el sufijo más pequeño posible. En nuestro ejemplo, esto será (0, 2, 3, 5) y la secuencia completa se verá como (0, 1, 3, 0, 2, 3, 5).
   

Este valor será el próximo reordenamiento lexicográfico.



En cuanto a la aplicación práctica del algoritmo, durante todo el tiempo de mi trabajo nunca lo he necesitado, pero para una entrevista con Uber pensaron lo contrario :))

Para simplificar, todo el código se escribirá en Go, y creo que es fácil para cualquiera traducirlo a cualquier otro lenguaje de programación.

Muchas gracias a PYXRU y 646f67 por meterme con una nariz en una posible optimización del algoritmo, para calcular la permutación de la complejidad lineal simplemente haciendo el sufijo inverso.

func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }