Permutări prin backtracking la BAC: program C++

Generarea permutărilor prin backtracking înseamnă construirea tuturor ordonărilor elementelor, fără repetarea unei valori în aceeași soluție. La BAC, formula factorialului îți spune câte permutări există, dar nu descrie singură algoritmul care le afișează. Pentru generare trebuie să urmărești poziția curentă, valorile folosite și revenirea după fiecare alegere.

Lecția privește backtrackingul de la matematică-informatică. Vom genera permutările numerelor de la unu la n, pentru n între unu și opt, în ordine lexicografică. După înțelegerea schemei, compară fiecare condiție cu cea dintr-un subiect de BAC la informatică, mai ales dacă apar restricții suplimentare.

Ce reprezintă soluția parțială

Păstrăm într-un vector valorile alese pentru primele poziții. La nivelul curent trebuie completată o singură poziție. Valorile de pe pozițiile anterioare formează un prefix valid și nu trebuie schimbate cât timp explorăm completările lui.

Pentru n egal cu trei, prefixul unu, trei este valid și poate fi completat numai cu doi. Prefixul unu, unu nu este valid, deoarece aceeași valoare ar apărea de două ori în permutare.

Un tablou de marcaje spune pentru fiecare valoare dacă a fost deja folosită în prefixul curent. Marcajul se referă la valoare, nu la poziția pe care încercăm să o completăm. Această distincție este esențială pentru testul de validitate.

Alegere, explorare, anulare

Pentru fiecare candidat nefolosit, îl scriem pe poziția curentă și îl marcăm drept folosit. Apelul recursiv explorează toate completările posibile după această alegere. La întoarcere, anulăm marcajul pentru a permite folosirea valorii în alte ramuri.

Anularea nu șterge o soluție deja afișată. Ea restabilește starea prefixului anterior, astfel încât următorul candidat să fie evaluat în aceleași condiții. Fără această revenire, valorile ar rămâne blocate de ramuri terminate.

Etapă	Ce se schimbă
Alegere	Scrii candidatul și activezi marcajul lui
Explorare	Completezi recursiv pozițiile următoare
Revenire	Dezactivezi marcajul candidatului

Nu trebuie să resetezi întregul tablou de marcaje după fiecare ramură. Valorile prefixului anterior trebuie să rămână marcate. Anulezi doar alegerea făcută la nivelul din care revii.

Program C++ complet

Vectorul soluției și marcajele sunt comune apelurilor, iar disciplina de marcare și demarcare păstrează starea corectă. Pozițiile soluției sunt numerotate de la unu. Când poziția curentă depășește n, toate pozițiile au fost completate.

#include <iostream>
using namespace std;

int n, x[9];
bool folosit[9] = {};

void genereaza(int k) {
    if (k > n) {
        for (int i = 1; i <= n; ++i) {
            if (i > 1) cout << ' ';
            cout << x[i];
        }
        cout << '\n';
        return;
    }
    for (int valoare = 1; valoare <= n; ++valoare) {
        if (!folosit[valoare]) {
            x[k] = valoare;
            folosit[valoare] = true;
            genereaza(k + 1);
            folosit[valoare] = false;
        }
    }
}

int main() {
    cin >> n;
    genereaza(1);
    return 0;
}

Programul presupune elemente distincte, exact numerele de la unu la n. Dacă ai o listă cu valori repetate, marcarea pozițiilor acelei liste nu ar elimina automat soluțiile identice ca valori. Ar fi o altă problemă de generare, cu reguli suplimentare pentru duplicate.

Ordinea soluțiilor pentru n egal cu trei

Primul candidat de pe prima poziție este unu. Pe a doua poziție se încearcă mai întâi doi, iar ultima poziție primește trei. Prima soluție este unu, doi, trei.

După revenire, se explorează prefixul unu, trei, care produce unu, trei, doi. Abia după terminarea tuturor soluțiilor care încep cu unu se trece la prima valoare doi. Ordinea completă este:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Ordinea lexicografică compară prima poziție la care două soluții diferă. Parcurgerea crescătoare a candidaților, combinată cu explorarea completă a fiecărui prefix înaintea următorului, produce această ordine.

De ce fiecare permutare apare o singură dată

O soluție completă are n valori distincte alese dintr-o mulțime cu n elemente. Prin urmare, conține toate elementele exact o dată. Marcajele garantează că nu se repetă valori în interiorul unei soluții.

Fiecare permutare posibilă determină un traseu unic de alegeri, citit de la stânga la dreapta. Algoritmul încearcă acel candidat la fiecare nivel, deoarece nu a apărut în prefixul permutării. Astfel, nicio permutare validă nu este omisă.

Două trasee diferite aleg valori diferite pe cel puțin o poziție și produc soluții diferite. Acesta este argumentul pentru lipsa dublurilor, separat de argumentul că fiecare soluție respectă proprietatea.

Erori de revenire

Dacă omiți demarcarea după apel, un candidat folosit într-o ramură poate rămâne indisponibil în ramurile următoare. Programul poate afișa prima soluție corect și apoi să piardă multe dintre celelalte, ceea ce face eroarea mai puțin evidentă într-o verificare superficială.

Dacă demarchezi înaintea apelului recursiv, valoarea nu mai apare ca folosită în timpul completării și poate fi aleasă din nou. Ai permite repetări, încălcând definiția permutării.

Dacă ștergi toate marcajele la revenire, pierzi și informația despre prefixul care trebuie păstrat. Ordinea corectă este locală: marchezi alegerea curentă, explorezi, apoi anulezi exact acel marcaj.

Nivelul de afișare

Soluția se afișează numai după completarea tuturor pozițiilor. Un prefix precum unu, doi pentru n egal cu trei nu este o permutare completă. Afișarea lui ar amesteca soluțiile parțiale cu cele finale.

Poți organiza baza și ca verificare a ultimei poziții completate, dar atunci apelul inițial și momentul afișării trebuie adaptate consecvent. Nu combina limita unei variante cu semnificația nivelului din alta.

Scrie într-o propoziție ce înseamnă parametrul k: în programul nostru, este poziția care urmează să fie completată. Această propoziție permite verificarea tuturor limitelor fără memorarea mecanică a unei forme de cod.

Numărul soluțiilor și costul afișării

Există n factorial permutări. Pentru n egal cu patru, programul trebuie să afișeze douăzeci și patru de linii, iar pentru n egal cu cinci, o sută douăzeci. Numărul liniilor este o verificare utilă, dar trebuie controlată și unicitatea lor.

Afișarea fiecărei soluții cere scrierea a n valori. Timpul total nu poate fi mai mic decât volumul ieșirii, iar pentru această generare este de ordinul n înmulțit cu n factorial. Memoria vectorului, marcajelor și stivei este proporțională cu n.

Nu spune că algoritmul este liniar fiindcă are n niveluri. Adâncimea unui traseu și numărul total al traseelor sunt mărimi diferite. Această distincție sprijină înțelegerea algoritmului de generare.

Exerciții cu răspunsuri

n este unu. Există o singură soluție, formată din valoarea unu.

n este trei, iar prefixul este doi, trei. Singura completare este unu, deci soluția este doi, trei, unu.

n este patru, iar candidații sunt încercați descrescător. Prima soluție devine patru, trei, doi, unu. Schimbarea ordinii candidaților schimbă ordinea afișării, nu mulțimea permutărilor.

Întrebări frecvente

Trebuie să resetez și vectorul soluției la revenire?

Nu este necesar aici. Poziția curentă va fi suprascrisă înainte de folosire, iar afișarea se face numai pentru poziții completate. Marcajele trebuie însă restaurate corect.

Pot folosi formula factorialului în locul generării?

Doar dacă se cere numărul soluțiilor. Dacă se cer soluțiile efective sau o ordine de afișare, formula singură nu produce lista.

Cum verific lipsa dublurilor?

Pentru un caz mic, compară lista completă, numărul liniilor și faptul că fiecare linie conține toate valorile o singură dată. Poți analiza o implementare proprie cu un profesor de informatică.