Algoritmo: Como encontrar a próxima permutação lexicográfica

Se você descrever brevemente qual é a ordem lexicográfica, isso será classificado em ordem alfabética. I.e. a sequência de caracteres - AAA → AAB → AAC → AAD → ……… → WWW - é classificada em ordem alfabética (ou, no nosso caso, lexicográfica).

Imagine que você possui uma sequência finita de caracteres, por exemplo, 0, 1, 2, 5, 3, 3, 0 e precisa encontrar todas as permutações possíveis desses caracteres. O mais intuitivo, mas também o mais difícil, é o algoritmo recursivo, quando selecionamos o primeiro caractere da sequência e depois recursivamente o segundo, terceiro, etc., até que todos os caracteres da sequência sejam selecionados. É claro que a complexidade de um algoritmo desse tipo é O (n!).

Mas acontece que o algoritmo mais simples para gerar todas as permutações em ordem lexicográfica é começar pelo menor e calcular repetidamente a próxima permutação em vigor. Vamos ver como fazer isso.

Assim como ao calcular o próximo valor inteiro, devemos tentar aumentar o lado direito da sequência e deixar o lado esquerdo inalterado.

Como exemplo, considere a sequência acima - (0, 1, 2, 5, 3, 3, 0). Para obter a sequência mais alta que a original, basta reorganizar o primeiro e o segundo elementos, mas isso não é necessário, pois é possível reorganizar o segundo e o terceiro elementos e obter uma sequência mais próxima em ordem crescente. o que nos levará à próxima permutação mais próxima etc.

O algoritmo mais ideal nesse caso seria o seguinte:

1. Antes de tudo, você precisa encontrar o maior sufixo não crescente. No exemplo acima, isso seria - (5, 3, 3, 0). Se você tentar fazer alguma permutação nesta sequência, ela não será maior que a original.
   Vale dizer que você pode encontrar essa sequência no tempo O (n) olhando a sequência da esquerda para a direita.
2. O próximo elemento do sufixo é o ponto de articulação. No nosso caso, este é 2. O ponto de articulação será sempre menor que o primeiro elemento do sufixo. Isso significa que no sufixo certamente haverá um elemento que excede o ponto de articulação e se mudarmos o ponto de articulação para o menor elemento do sufixo que excede o elemento de suporte do ponto de articulação - obteremos uma sequência que excede a original - no nosso caso, será (0, 1, 3, 5 , 3, 2, 0).
   I.e. o resultado desta operação será o prefixo ascendente mínimo possível.
   
3. E na última etapa, precisamos classificar o sufixo em ordem crescente. I.e. obtemos o menor sufixo possível. No nosso exemplo, será (0, 2, 3, 5) e a sequência inteira será semelhante a (0, 1, 3, 0, 2, 3, 5).
   

Este valor será o próximo rearranjo lexicográfico.



Quanto à aplicação prática do algoritmo, durante todo o tempo do meu trabalho eu nunca precisei, mas para uma entrevista com a Uber eles pensaram o contrário :))

Por uma questão de simplicidade, todo o código será escrito em Go, e acho fácil para qualquer um traduzi-lo para qualquer outra linguagem de programação.

Muito obrigado a PYXRU e 646f67 por me cutucar com o nariz em uma possível otimização do algoritmo - para calcular a permutação para complexidade linear simplesmente executando o sufixo reverso.

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 }