Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes