Generarea permutărilor

O permutare folosește fiecare dintre cele $n$ valori distincte exact o dată, iar ordinea contează. Pentru $\{1,2,3\}$ există $3!=6$ permutări: 123, 132, 213, 231, 312, 321. La generare, înainte de a pune o valoare pe poziția curentă verificăm că nu este deja folosită.

O permutare a unei mulțimi cu $n$ elemente distincte este un șir în care fiecare element apare exact o dată, deci ordinea contează. Numărul permutărilor este $n!$: pe prima poziție sunt $n$ alegeri, pe a doua $n-1$ și așa mai departe, până la o singură alegere pe ultima. Pentru $n=3$ sunt $3!=6$ permutări, iar pentru $n=4$ sunt $4!=24$. Se generează prin backtracking cu un vector $x_1,\dots ,x_n$ și un vector de marcaje folosit: la nivelul $k$ se încearcă fiecare valoare $c$ de la 1 la $n$ care nu este încă folosită, se marchează, se apelează nivelul următor, iar după revenire marcajul se anulează. Dacă valorile sunt încercate în ordine crescătoare, permutările apar în ordine lexicografică.

Exemplul 1 — permutările lui $\{1,2,3\}$.

#include <iostream>
using namespace std;
int x[4];
bool folosit[4];
void gen(int k) {
    if (k == 4) {
        for (int i = 1; i <= 3; ++i) cout << x[i];
        cout << " ";
        return;
    }
    for (int c = 1; c <= 3; ++c)
        if (!folosit[c]) {
            folosit[c] = true;
            x[k] = c;
            gen(k + 1);
            folosit[c] = false;
        }
}
int main() {
    gen(1);
    return 0;
}

Programul afișează 123 132 213 231 312 321 . Apelul gen(1) începe cu 1, apoi gen(2) încearcă 2 și gen(3) pune 3: se afișează 123; la revenire, gen(2) încearcă 3 și gen(3) pune 2: se afișează 132. Apoi gen(1) încearcă 2, apoi 3. Marcajul se anulează la revenire, ca valoarea să poată fi folosită în alte ramuri.

Exemplul 2 — permutări cu o restricție. Se cer permutările lui $\{1,2,3,4\}$ în care valoarea 1 nu se află pe prima poziție. Condiția de continuare este k > 1 || c != 1, adică la nivelul 1 se respinge valoarea 1. Cele 24 de permutări se împart în 6 cu 1 pe prima poziție și 18 fără; programul cu restricție produce 18 soluții. Se obține tot astfel $4!-3!=24-6=18$: din toate permutările se scad cele care încep cu 1 și au $3!$ completări. Pentru $\{1,2,3\}$ și restricția „niciun element nu este pe poziția cu același număr” (permutări fără puncte fixe) există 2 soluții, 231 și 312.

Exemplul 3 — permutări circulare ale unui șir. Dacă se cere ca fiecare permutare să fie citită ca număr, permutările lui $\{1,2,3\}$ sunt numerele 123, 132, 213, 231, 312, 321, cu suma $1332$. Suma are o structură: fiecare cifră apare de două ori pe fiecare poziție, iar $2\cdot (1+2+3)\cdot 111=1332$. Verificarea prin formulă confirmă rezultatul unui program.

Exemplul 4 — numărul de apeluri. Pentru $n=3$, funcția gen se apelează de $1+3+6+6=16$ ori, iar pentru $n=4$ de 65 de ori. Cea mai mare parte a lucrului este în ultimele niveluri, de aceea numărul de permutări $n!$ crește foarte repede: pentru $n=10$ sunt 3 628 800 de permutări, iar generarea tuturor devine impracticabilă pentru valori mai mari ale lui $n$.

Exemplul 5 — elemente vecine. Câte permutări ale mulțimii $\{1,2,3,4\}$ au valorile 1 și 2 pe poziții alăturate? Cele două valori se tratează ca un bloc. Blocul și celelalte două valori formează trei obiecte, care se pot așeza în $3!=6$ moduri, iar în interiorul blocului ordinea este 12 sau 21, deci în 2 moduri. Rezultă $6\cdot 2=12$ permutări, dintre care 1234, 2134 și 3412. Un program care generează toate cele 24 de permutări și numără doar pe cele cu valorile 1 și 2 vecine confirmă același număr.

La numărare, pe prima poziție sunt $n$ alegeri, pe următoarea $n-1$ și așa mai departe, deci $n!$ permutări. Dacă enunțul include valori identice, nu aplica automat formula $n!$ pentru rezultate distincte; trebuie tratate repetițiile. Când se cere numărul permutărilor cu o restricție, numără complementul, adică permutările care încalcă restricția, și scade din $n!$. Dacă o restricție fixează un element pe o poziție, restul de $n-1$ elemente se permută liber. În ordinea lexicografică, permutarea de rang $m$ se află numărând prefixurile: pentru $n=3$, prima cifră este 1 pentru permutările de rang 1–2, 2 pentru rang 3–4 și 3 pentru rang 5–6; deci a cincea permutare este 312.

Exemplu în formatul examenului. Câte permutări ale mulțimii $\{1,2,3,4\}$ se obțin dacă se generează toate permutările cu condiția ca valoarea 1 să nu apară pe prima poziție?

• a) 6
• b) 12
• c) 18
• d) 24

Răspunsul corect este c). Din cele $4!=24$ de permutări, cele care au 1 pe prima poziție sunt $3!=6$, pentru că celelalte trei valori se permută liber pe ultimele trei poziții. Rămân $24-6=18$ permutări. Altfel: pe prima poziție se poate pune oricare dintre valorile 2, 3, 4 (3 alegeri), iar pe celelalte trei poziții se permută cele 3 valori rămase, deci $3\cdot 3!=18$. Varianta d) ignoră restricția, iar varianta a) numără permutările excluse.

Greșeli frecvente

• Greșit: o permutare poate repeta o valoare.
  Corect: fiecare element al mulțimii apare exact o dată.
• Greșit: marcajul unei valori se păstrează după revenirea din apel.
  Corect: se anulează, altfel valoarea nu mai poate apărea în alte ramuri.
• Greșit: numărul permutărilor de $n$ elemente este $n^2$.
  Corect: este $n!$.

Înainte și după