CKTIS / C++
std::next_permutation — permutação lexicográfica seguinte
std::next_permutation reorganiza um intervalo segundo a permutação lexicográfica seguinte. Devolve true se existir uma sucessora; depois da última permutação, repõe a primeira disposição e devolve false.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <algorithm>
template<class BidirectionalIterator>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);std::next_permutation, de <algorithm>, modifica diretamente o intervalo [first, last). A ordem lexicográfica de duas disposições é determinada pela primeira posição em que os seus elementos não são equivalentes segundo a comparação utilizada. A sobrecarga sem comp utiliza a comparação predefinida «menor que»; a sobrecarga com comp define a ordem através desse comparador.
Um resultado true significa que foi encontrada uma disposição seguinte. Um resultado false não significa que os dados tenham ficado inalterados: o algoritmo repõe a primeira disposição, ordenada por ordem crescente segundo a comparação utilizada. Um intervalo vazio ou com um único elemento devolve false.
Os iteradores têm de ser bidirecionais e os elementos referenciados têm de permitir a troca de valores. comp tem de definir uma ordem fraca estrita; não utilize <=. Para N elementos, a norma limita o número de trocas a N / 2.
Comece com um intervalo ordenado segundo a mesma comparação e utilize do–while para que a disposição inicial também seja processada. O ciclo percorre uma disposição por cada sequência distinta de classes de equivalência definidas pela comparação. Se a comparação considerar equivalentes valores diferentes, o ciclo pode omitir algumas sequências distintas de valores. No exemplo, a comparação predefinida distingue 1 de 2, pelo que o ciclo imprime as três disposições distintas dos valores. O exemplo também mostra o estado após a chamada final devolver false.
Exemplos
#include <algorithm>
#include <array>
#include <iostream>
int main() {
std::array<int, 3> values{1, 1, 2};
do {
std::cout << values[0] << ' ' << values[1] << ' '
<< values[2] << '\n';
} while (std::next_permutation(values.begin(), values.end()));
std::cout << "reset: " << values[0] << ' ' << values[1]
<< ' ' << values[2] << '\n';
}
Resultado
1 1 2 1 2 1 2 1 1 reset: 1 1 2
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.