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

CKTIS / C++

std::prev_permutation — permutação lexicográfica anterior

std::prev_permutation reorganiza um intervalo na sua permutação lexicográfica anterior. Devolve bool; quando não existe uma permutação anterior, reorganiza o intervalo na última permutação e devolve false.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <algorithm>

template<class BidirectionalIterator>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
constexpr bool prev_permutation(BidirectionalIterator first,
                                BidirectionalIterator last,
                                Compare comp);

std::prev_permutation, declarada em <algorithm>, modifica [first, last) no próprio intervalo para produzir a disposição imediatamente anterior por ordem lexicográfica. A ordem é determinada pela primeira posição em que os valores não são equivalentes segundo o comparador. Em C++23, o comparador predefinido é std::less{}, que garante uma ordem total estrita para os ponteiros, mesmo quando o operador nativo < não a garante. A sobrecarga que recebe comp permite fornecer outra ordenação estrita fraca.

Um valor de retorno true significa que foi encontrada uma permutação anterior. Um valor de retorno false não significa que os dados tenham ficado inalterados: o algoritmo produz a última permutação, por ordem decrescente segundo a ordenação escolhida. Para um intervalo vazio ou com um único elemento, devolve false e o conteúdo mantém-se igual.

O algoritmo requer iteradores bidirecionais cujos valores referenciados possam ser trocados. Não é necessário ordenar os dados antes de executar um único passo. Se o comparador distinguir todos os pares de valores distintos no intervalo, parta da ordem decrescente e use um ciclo do–while para percorrer cada disposição distinta dos valores exatamente uma vez, da maior para a menor. Se o comparador considerar equivalentes valores distintos, o algoritmo distingue apenas as disposições das respetivas classes de equivalência e pode, por isso, saltar algumas disposições dos valores. Por exemplo, se o intervalo contiver apenas dois valores distintos que o comparador considere equivalentes, logo a primeira chamada devolve false.

O exemplo mostra tanto as transições entre permutações como o retorno à última permutação depois de false. Esta entrada descreve as sobrecargas de std::prev_permutation que devolvem bool, não a interface std::ranges.

Exemplos

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    std::array<int, 3> values{2, 1, 1};
    std::cout << std::boolalpha;

    bool found;
    do {
        for (int value : values) {
            std::cout << value;
        }
        found = std::prev_permutation(values.begin(), values.end());
        std::cout << " -> " << found << '\n';
    } while (found);

    std::cout << "after wrap: ";
    for (int value : values) {
        std::cout << value;
    }
    std::cout << '\n';
}

Resultado

211 -> true
121 -> true
112 -> false
after wrap: 211

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