std::next_permutation Explicación de la implementación

El algoritmo std::next_permutation calcula la siguiente permutación lexicográficamente más grande de una secuencia dada. Comprender su implementación es crucial para comprender su comportamiento.

Esquema del algoritmo

El algoritmo itera sobre la secuencia de derecha a izquierda, buscando el "ascendente" más a la izquierda (es decir, , un elemento que es más pequeño que su sucesor). Si no se encuentra ningún ascendente, significa que la secuencia está en orden decreciente, en cuyo caso se invierte la secuencia para obtener la permutación más pequeña.

De lo contrario, el algoritmo continúa encontrando el elemento más pequeño en la secuencia a la derecha del ascendente (llamado "k"). Luego, este elemento se intercambia con el ascendente. Finalmente, los elementos a la derecha del ascendente se invierten para mantener el orden decreciente.

Roles variables

• i: Puntos a el elemento actual que se está examinando.
• j: Apunta al elemento inmediatamente anterior i.
• k: Apunta al elemento más pequeño en la secuencia a la derecha de i cuando i es un ascendente.

Flujo de bucle

El bucle se repite hasta que llego al comienzo de la secuencia (comienzo). Dentro de cada iteración:

1. Si i no es un ascendente, disminuye i y j.
2. Si i es un ascendente, encuentra el elemento más pequeño a la derecha de i (k ), lo intercambia con i e invierte todo lo que está a la derecha de i.

Ejemplo

Considere la secuencia {1, 2, 4, 3}.

• Iteración 1: i está inicialmente en 3. j está en 2. Dado que 3
• Iteración 2: se encuentra que k es 2. 3 se intercambia con 2. {1, 3, 4, 2}. Los elementos a la derecha de 3 (4 y 2) están invertidos. {1, 3, 2, 4}.
• Iteración 3: i disminuye y j disminuye. i ahora está en 2. j está en 1. 2
• Iteración 4: se encuentra que k es 1. 2 se intercambia por 1. { 1, 2, 4, 3}. Los elementos a la derecha de 2 (4 y 3) están invertidos. {1, 2, 3, 4}.
• Iteración 5: i disminuye y j disminuye. i ahora está en 1. j está al comienzo de la secuencia. Como no hay más ascendentes, la secuencia se invierte. {4, 3, 2, 1}.