Generarea soluțiilor — permutări, combinări, aranjamente

Generarea ca backtracking

În capitolul de combinatorică ai învățat să numeri: câte permutări (n!), câte combinări (C(n, k)). Aici facem pasul următor — le generăm efectiv, una câte una.

Ideea e mereu aceeași schemă din capitol, „alege — recursie — dezalege”: construiești soluția poziție cu poziție, într-un vector global sol[]. Pe fiecare poziție încerci, pe rând, toate valorile valide; pentru fiecare alegere cobori recursiv pe poziția următoare; când ai umplut toate pozițiile, ai o soluție completă pe care o afișezi.

Diferența dintre tipurile de soluții nu stă în schemă, ci în regula care decide ce valori sunt valide pe poziția curentă.

Permutări cu folosit[] vs combinări cu ordine crescătoare

Aceasta este distincția esențială a lecției.

Permutări — folosești fiecare element exact o dată, dar orice ordine contează ca soluție distinctă. Ca să nu pui același element de două ori, ții un vector folosit[]: înainte de a alege valoarea i verifici folosit[i] == false, o marchezi, cobori recursiv, iar la întoarcere o dezmarchezi. Pentru {1,2,3} obții și 1 2 3, și 3 2 1 — sunt permutări diferite.

Combinări — contează doar setul de elemente, nu ordinea. Aici {1,2} și {2,1} sunt aceeași soluție, deci nu vrei să le generezi pe amândouă. Trucul: impui o ordine crescătoare. Pe fiecare poziție pornești de la valoarea start = ultima_aleasă + 1, nu de la 1. Așa fiecare set apare exact o dată, în forma lui crescătoare.

Exemplu pas cu pas

Permutările lui {1, 2, 3} (3 poziții, fiecare valoare o dată):

poz 0 = 1 -> poz 1 = 2 -> poz 2 = 3   => 1 2 3
                       2 -> ...  3      (2 deja folosit, se sare)
          poz 1 = 3 -> poz 2 = 2        => 1 3 2
poz 0 = 2 -> ...                        => 2 1 3, 2 3 1
poz 0 = 3 -> ...                        => 3 1 2, 3 2 1

Rezultat: 6 permutări (adică 3! = 6).

Combinările de 2 din {1, 2, 3} (2 poziții, ordine crescătoare):

poz 0 = 1 -> poz 1 pornește de la 2 -> {1,2}, {1,3}
poz 0 = 2 -> poz 1 pornește de la 3 -> {2,3}
poz 0 = 3 -> nu mai există valoare > 3 pentru poz 1 -> nimic

Rezultat: 3 combinări (adică C(3,2) = 3). Observă cum start crescător taie din start dublurile precum {2,1}.

Implementare C++

Două funcții independente: permutari (cu folosit[]) și combinari (cu start).

#include <iostream>
using namespace std;

int n, k;
int sol[20];           // solutia construita, pozitie cu pozitie
bool folosit[20];      // folosit[i] = a fost valoarea i pusa deja in solutie?

void afiseaza(int lungime) {
    for (int i = 0; i < lungime; i++) {
        cout << sol[i] << " ";
    }
    cout << "\n";
}

// PERMUTARI: orice ordine, fiecare valoare 1..n exact o data
void permutari(int poz) {
    if (poz == n) {          // toate pozitiile umplute -> solutie completa
        afiseaza(n);
        return;
    }
    for (int val = 1; val <= n; val++) {
        if (!folosit[val]) {     // valoarea inca nu e in solutie
            sol[poz] = val;      // alege
            folosit[val] = true;
            permutari(poz + 1);  // recursie
            folosit[val] = false; // dezalege (pas obligatoriu!)
        }
    }
}

// COMBINARI: doar setul conteaza, ordine crescatoare prin "start"
void combinari(int poz, int start) {
    if (poz == k) {          // am ales k elemente -> set complet
        afiseaza(k);
        return;
    }
    for (int val = start; val <= n; val++) {
        sol[poz] = val;            // alege
        combinari(poz + 1, val + 1); // recursie: urmatoarea valoare > val
        // fara folosit[] si fara dezalegere: "start" garanteaza unicitatea
    }
}

int main() {
    n = 3;
    cout << "Permutarile lui {1,2,3}:\n";
    permutari(0);              // afiseaza 6 permutari

    k = 2;
    cout << "Combinarile de 2 din {1,2,3}:\n";
    combinari(0, 1);           // afiseaza 3 combinari: 1 2 / 1 3 / 2 3
    return 0;
}

Complexitate

Costul e dat de numărul de soluții generate (le parcurgi pe toate):

• Permutări: O(n!) — există n! permutări, iar fiecare se afișează în O(n).
• Combinări: O(C(n, k)) — atâtea seturi distincte, fiecare afișat în O(k).
• Aranjamente: O(n! / (n-k)!) — orice ordine, dar doar k elemente alese.

Numerele cresc exploziv: pentru n = 10, 10! = 3 628 800 permutări. Generarea completă e fezabilă doar pentru n mic.

Diagrama de mai jos arată un instantaneu al vectorului folosit[] în timpul generării permutărilor, după ce ai ales sol = [1, 3, _] (valorile 1 și 3 sunt marcate, 2 e liber):

Recapitulare

• Generarea = construiești soluția poziție cu poziție cu schema „alege — recursie — dezalege”, în sol[] global; diferă doar regula valorilor valide.
• Permutări: folosit[] (orice ordine, fiecare o dată, marchezi + dezmarchezi); combinări: start = val + 1 (ordine crescătoare, fără duplicate de seturi).
• Costul = numărul de soluții: permutări O(n!), combinări O(C(n,k)) — fezabil doar pentru n mic.