Permutări, aranjamente și combinări prin backtracking

Permutările, aranjamentele și combinările sunt cele trei generări clasice prin backtracking și stau la baza aproape oricărui item de backtracking de la BAC Informatică. Partea frumoasă este că toate pornesc de la aceeași schemă în C++; diferă doar două-trei rânduri. Dacă știi exact ce rânduri schimbi și de ce, poți recunoaște imediat tipul de generare dintr-un enunț și poți prezice ordinea soluțiilor.

Mai întâi, ce numărăm

Fie o mulțime cu n elemente. Întrebarea-cheie este: contează ordinea și câte elemente iau?

Exemplu concret pentru n = 4 și p = 2: există 4! = 24 de permutări, A(4,2) = 12 aranjamente și C(4,2) = 6 combinări. Între aranjamente și combinări există relația A(n,p) = C(n,p) · p!, pentru că fiecare submulțime de p elemente poate fi ordonată în p! moduri.

Schema comună

Pornim de la funcția recursivă standard: back(k) încearcă toate valorile pentru poziția k a vectorului st, păstrează doar valorile valide și afișează când soluția e completă. Diferențele dintre cele trei generări se reduc la trei întrebări: ce valori încerci, ce verifici și când te oprești.

1. Permutări

• Valori: de la 1 la n pe fiecare poziție.
• Validare: st[k] diferit de toate st[1]…st[k-1].
• Soluție: când k == n.

Pentru n = 3 se obțin, în ordine: 123, 132, 213, 231, 312, 321.

2. Aranjamente

Singura diferență față de permutări este momentul în care te oprești: soluția are doar p elemente.

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        st[k] = v;
        if (valid(k))          // aceeași validare ca la permutări
        {
            if (k == p)        // aici e diferența
                afisare();     // afișează st[1]..st[p]
            else
                back(k + 1);
        }
    }
}

Pentru n = 4 și p = 2 se generează: 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43. Observă că apar și 12, și 21: ordinea contează.

3. Combinări

La combinări, {1, 2} și {2, 1} sunt aceeași submulțime, deci trebuie generată o singură dată. Truc: generezi doar șiruri strict crescătoare. Dacă fiecare element este mai mare decât precedentul, elementele sunt automat distincte, așa că funcția valid nici nu mai e necesară. Pur și simplu pornești bucla de la st[k-1] + 1.

#include <iostream>
using namespace std;

int n, p, st[20];   // st[0] = 0, fiind variabilă globală

void afisare()
{
    for (int i = 1; i <= p; i++)
        cout << st[i] << ' ';
    cout << '\n';
}

void back(int k)
{
    for (int v = st[k - 1] + 1; v <= n - p + k; v++)
    {
        st[k] = v;
        if (k == p)
            afisare();
        else
            back(k + 1);
    }
}

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

De ce limita superioară este n - p + k și nu n? Pe poziția k trebuie să mai rămână loc pentru p − k valori mai mari în dreapta. De exemplu, pentru n = 5 și p = 3, pe prima poziție nu are rost să pui 4 sau 5, pentru că nu mai ai două valori mai mari după ele. Cu limita n - p + k, poziția 1 merge până la 3, poziția 2 până la 4, poziția 3 până la 5. Programul ar fi corect și cu limita n, doar că ar face încercări inutile.

Pentru n = 5 și p = 3 se afișează cele C(5,3) = 10 soluții: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

Rezumatul diferențelor

Ultimul rând, produsul cartezian, apare când elementele se pot repeta: de exemplu, toate numerele de 3 cifre formate doar din cifrele 1 și 2 (111, 112, 121, 122, 211, …). Sunt nᵖ soluții, aici 2³ = 8.

Când elementele nu sunt numerele 1…n

În enunțuri apar frecvent mulțimi de cuvinte, culori sau cifre oarecare. Soluția este simplă: generezi indici de la 1 la n și afișezi elementul corespunzător. De exemplu, pentru culorile {roșu, galben, verde, albastru} memorate în char c[5][10] (pe pozițiile 1…4), funcția de afișare devine:

void afisare()
{
    for (int i = 1; i <= p; i++)
        cout << c[st[i]] << ' ';
    cout << '\n';
}

Combinările de câte 2 vor fi afișate în ordinea dată de indici: (roșu, galben), (roșu, verde), (roșu, albastru), (galben, verde), (galben, albastru), (verde, albastru). Ordinea soluțiilor urmează ordinea elementelor din mulțimea dată, nu ordinea alfabetică, un detaliu care schimbă răspunsul la multe grile.

Condiții suplimentare

Cerințele reale combină de obicei o generare de bază cu o restricție: „numere de 3 cifre distincte cu suma cifrelor pară”, „submulțimi în care nu apar două numere consecutive”. Procedezi așa: identifici întâi generarea de bază (aranjamente, combinări etc.), apoi adaugi restricția fie în valid (dacă se poate verifica pe parcurs, ca la „două elemente vecine”), fie la momentul soluției (dacă depinde de toate elementele, ca la „suma cifrelor”).