std::next_permutation în C++

bool next_permutation(BidirIt first, BidirIt last);
bool prev_permutation(BidirIt first, BidirIt last);

Ce face std::next_permutation

std::next_permutation rearanjează elementele în permutarea imediat următoare în ordinea „de dicționar”. Returnează true dacă a existat o permutare următoare; după ultima (ordinea descrescătoare) revine la prima (crescătoare) și returnează false.

Pentru a genera toate permutările, sortezi crescător și apelezi într-o buclă do { ... } while (std::next_permutation(...));. std::prev_permutation merge în sens invers.

Parametri

Parametru	Descriere
first, last	Intervalul permutat.

Ce returnează

true dacă s-a trecut la o permutare nouă, false dacă s-a revenit la început.

Exemple

Exemplul 1: Toate ordinile posibile

#include <algorithm>
#include <print>
#include <string>

int main() {
    std::string litere = "abc";
    int numar = 0;

    do {
        std::print("{} ", litere);
        ++numar;
    } while (std::next_permutation(litere.begin(), litere.end()));

    std::println("\nTotal: {} permutări", numar);
}

Rezultat

abc acb bac bca cab cba 
Total: 6 permutări

Exemplul 2: Următoarea și precedenta

Elementele repetate sunt tratate corect: nu se generează permutări duplicate.

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{1, 3, 2};

    std::next_permutation(v.begin(), v.end());
    std::println("Următoarea după 1 3 2: {}", v);

    std::ranges::prev_permutation(v);
    std::ranges::prev_permutation(v);
    std::println("Două înapoi: {}", v);

    std::vector<int> d{1, 1, 2};
    int total = 0;
    do {
        ++total;
    } while (std::ranges::next_permutation(d).found);
    std::println("Permutări distincte pentru 1 1 2: {}", total);
}

Rezultat

Următoarea după 1 3 2: [2, 1, 3]
Două înapoi: [1, 2, 3]
Permutări distincte pentru 1 1 2: 3

Greșeli frecvente

• Nu sortezi înainte de bucla do-while și pierzi permutările mai „mici” decât ordinea inițială.
• Folosești while (next_permutation(...)) { ... } în loc de do-while și sari peste prima permutare.

Comenzi înrudite

• std::is_permutation: Verifică dacă două intervale conțin aceleași elemente, de același număr de ori, în orice ordine.
• std::sort: Sortează elementele dintr-un interval, crescător sau după o regulă dată de tine.
• std::lexicographical_compare: Compară două intervale ca în dicționar și spune dacă primul vine înaintea celui de-al doilea.