1
1. Ce este o permutare?
O permutare a multimii {1, 2, ..., n} este o aranjare a tuturor celor n elemente intr-o ordine anume. Fiecare element apare exact o data.
Exemplu: Permutarile lui {1, 2, 3}
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Total: 3! = 3 × 2 × 1 = 6 permutari
Formula: Numarul de permutari ale lui n elemente este n! (n factorial).
Cresterea lui n! (output real, Python):
n=1: 1 permutari n=2: 2 permutari n=3: 6 permutari n=4: 24 permutari n=5: 120 permutari n=6: 720 permutari n=7: 5040 permutari n=8: 40320 permutari
Atentie: n! creste exploziv. Algoritmul devine lent pentru n > 12 in aplicatii de timp real.
2
2. Ideea algoritmului: constructie pozitie cu pozitie
Construim permutarea pas cu pas: la pasul
k decidem ce element punem pe pozitia k. Incercam pe rand fiecare element nefolosit inca. Daca ajungem la o solutie completa (toate n pozitiile ocupate), o afisam, apoi revenim (backtrack) si incercam urmatoarea optiune.
Arborele de cautare pentru n=2 (output real, Python):
Pun 1 pe pozitia 0
Pun 2 pe pozitia 1
=> Solutie: [1, 2]
Revin: scot 2 de pe pozitia 1
Revin: scot 1 de pe pozitia 0
Pun 2 pe pozitia 0
Pun 1 pe pozitia 1
=> Solutie: [2, 1]
Revin: scot 1 de pe pozitia 1
Revin: scot 2 de pe pozitia 0
Ingredientele esentiale ale algoritmului:
- perm[k] — elementul ales pentru pozitia k
- folosit[i] — True daca elementul i este deja pe o pozitie
- back(pas) — functia recursiva: genereaza pozitia
passi toate cele urmatoare - Caz de baza: daca
pas == n, avem o solutie completa - Revenire: dupa exploatarea ramurii, dezactivam marcajul si incercam urmatorul element
3
3. Implementarea completa in Python
# Generarea permutarilor prin backtracking # Limbaj: Python | Nivel: mat-info cls XI def permutari(n): perm = [0] * n # vectorul solutie, indexat 0..n-1 folosit = [False] * (n + 1) # folosit[i]=True daca i e pe o pozitie rezultate = [] def back(pas): if pas == n: rezultate.append(perm[:]) # copie a solutiei curente return for i in range(1, n + 1): if not folosit[i]: perm[pas] = i folosit[i] = True back(pas + 1) perm[pas] = 0 # revenire: eliberam pozitia folosit[i] = False # revenire: eliberam marcajul back(0) return rezultate # Generam permutarile lui {1,2,3} n = 3 sol = permutari(n) print(f"Permutarile lui {1,...,{n}} ({len(sol)} bucati):") for p in sol: print(' '.join(map(str, p)))
Output real (rulat cu python):
Permutarile lui {1,...,3} (6 bucati):
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Observatie: Permutarile sunt generate in ordine lexicografica deoarece iteram candidatii i de la 1 la n in ordine crescatoare.
4
4. Permutari cu restrictii: taiere de ramuri (pruning)
Puterea backtracking-ului sta in taierea ramurilor (pruning): daca un candidat nu poate duce la o solutie valida, il sarim inainte de a-l explora recursiv. Adaugam o verificare suplimentara inainte de apelul
back(pas+1).
Exemplu: Permutari fara doua numere pare consecutive
# Permutari fara doua pare consecutive def permutari_restrictie(n): perm = [0] * n folosit = [False] * (n + 1) rezultate = [] def back(pas): if pas == n: rezultate.append(perm[:]) return for i in range(1, n + 1): if not folosit[i]: # Conditie de taiere: nu doua pare consecutive if pas > 0 and perm[pas-1] % 2 == 0 and i % 2 == 0: continue # taiem aceasta ramura perm[pas] = i folosit[i] = True back(pas + 1) perm[pas] = 0 folosit[i] = False back(0) return rezultate n = 4 sol = permutari_restrictie(n) print(f"Permutari de 4 fara doua pare consecutive ({len(sol)} bucati):") for p in sol: print(' '.join(map(str, p)))
Output real (rulat cu python):
Permutari de 4 fara doua pare consecutive (12 bucati): 1 2 3 4 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 3 2 1 4 3 4 1 2 4 1 2 3 4 1 3 2 4 3 1 2 4 3 2 1
Din cele 24 permutari posibile ale lui {1,2,3,4}, doar 12 respecta conditia. Backtracking-ul a evitat sa mai exploreze ramurile invalide, reducand efortul la jumatate in acest caz.
5
5. Complexitate si limite practice
Complexitate temporala: O(n · n!)
Exista n! permutari distincte. Fiecare permutare are n elemente, deci afisarea/copierea ei costa O(n). Suma totala: n × n! operatii.
Exista n! permutari distincte. Fiecare permutare are n elemente, deci afisarea/copierea ei costa O(n). Suma totala: n × n! operatii.
Numar de permutari pentru diverse valori ale lui n:
n=1: 1 permutari n=2: 2 permutari n=3: 6 permutari n=4: 24 permutari n=5: 120 permutari n=6: 720 permutari n=7: 5040 permutari n=8: 40320 permutari
Limite practice:
- n ≤ 8: instant (sub 1 secunda)
- n = 10: 3.628.800 permutari — cateva secunde
- n = 12: 479.001.600 permutari — minute sau ore
- n > 12: practic imposibil de enumerat toate
6
6. Implementare C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul mat-info intensiv, acelasi algoritm se implementeaza in C++ cu tablouri statice si functie recursiva globala. Diferente fata de Python: tipuri explicite, tablouri de dimensiune fixa, bool explicit.
#include <iostream> using namespace std; int n; int perm[10]; // solutia curenta, pozitii 0..n-1 bool folosit[10]; // marcaj elemente 1..n void back(int pas) { if (pas == n) { for (int i = 0; i < n; i++) { cout << perm[i]; if (i < n - 1) cout << " "; } cout << "\n"; return; } for (int i = 1; i <= n; i++) { if (!folosit[i]) { perm[pas] = i; folosit[i] = true; back(pas + 1); perm[pas] = 0; // revenire folosit[i] = false; // revenire } } } int main() { n = 3; cout << "Permutarile lui {1,2,3}:\n"; back(0); return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Permutarile lui {1,2,3}:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Acelasi output ca versiunea Python — algoritmul este identic, doar sintaxa difera. In C++, variabilele globale int perm[10] si bool folosit[10] sunt initializate automat cu 0 / false.