std::next_permutation Implementation Explication

O algoritmo std::next_permutation calcula a próxima permutação lexicograficamente maior de uma determinada sequência. Compreender sua implementação é crucial para entender seu comportamento.

Esboço do algoritmo

O algoritmo itera sobre a sequência da direita para a esquerda, procurando pelo "ascendente" mais à esquerda (ou seja, , um elemento menor que seu sucessor). Se nenhum ascendente for encontrado, significa que a sequência está em ordem decrescente, caso em que inverte a sequência para obter a menor permutação.

Caso contrário, o algoritmo continua encontrando o menor elemento na sequência à direita do ascendente (chamado "k"). Este elemento é então trocado pelo ascendente. Finalmente, os elementos à direita do ascendente são invertidos para manter a ordem decrescente.

Funções variáveis

• i: Aponta para o elemento atual que está sendo examinado.
• j: Aponta para o elemento imediatamente antes de i.
• k: Aponta para o menor elemento na sequência à direita de i quando i é um ascendente.

Loop Flow

O loop itera até i atingir o início da sequência (início). Dentro de cada iteração:

1. Se i não for um ascendente, ele decrementa i e j.
2. Se i for um ascendente, ele encontra o menor elemento à direita de i (k ), troca por i e inverte tudo à direita de i.

Exemplo

Considere a sequência {1, 2, 4, 3} .

• Iteração 1: i está inicialmente em 3. j está em 2. Como 3
• Iteração 2: k é considerado 2. 3 é trocado por 2. {1, 3, 4, 2}. Os elementos à direita de 3 (4 e 2) são invertidos. {1, 3, 2, 4}.
• Iteração 3: i é decrementado e j é decrementado. i agora está em 2. j está em 1. 2
• Iteração 4: k é considerado 1. 2 é trocado por 1. { 1, 2, 4, 3}. Os elementos à direita de 2 (4 e 3) são invertidos. {1, 2, 3, 4}.
• Iteração 5: i é decrementado e j é decrementado. i está agora em 1. j está no início da sequência. Como não há mais ascendentes, a sequência é invertida. {4, 3, 2, 1}.