1
1. Ce este o submultime?
O submultime a multimii A este orice multime B cu proprietatea ca orice element din B se afla si in A. Multimea vida {} si multimea A insasi sunt intotdeauna submultimi ale lui A.
Toate submultimile lui {1, 2, 3} (output real, Python si C++):
{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
Total: 23 = 8 submultimi
Formula generala: O multime cu
De ce 2n? Fiecare element are exact 2 optiuni: il includem sau nu. Deci avem 2 × 2 × … × 2 (de n ori) = 2n combinatii posibile.
n elemente are exact 2n submultimi (inclusiv {} si multimea insasi).De ce 2n? Fiecare element are exact 2 optiuni: il includem sau nu. Deci avem 2 × 2 × … × 2 (de n ori) = 2n combinatii posibile.
Cresterea lui 2^n (output real, Python):
n= 3: 2^n = 8 submultimi n= 4: 2^n = 16 submultimi n= 5: 2^n = 32 submultimi n= 8: 2^n = 256 submultimi n=10: 2^n = 1,024 submultimi n=20: 2^n = 1,048,576 submultimi n=30: 2^n = 1,073,741,824 submultimi
Atentie: 2n creste exponential. La n=30, peste un miliard de submultimi.
2
2. Ideea algoritmului backtracking pentru submultimi
Construim submultimea adaugand un element la un moment. La fiecare pas alegem un element i ≥ start. Inainte de orice candidat, inregistram solutia curenta (chiar daca e vida). Dupa fiecare extindere, revenim.
Arborele de cautare pentru n=2 (output real, Python):
=> Solutie: {}
Adaug 1: sol=[1]
=> Solutie: {1}
Adaug 2: sol=[1, 2]
=> Solutie: {1, 2}
Scot 2
Scot 1
Adaug 2: sol=[2]
=> Solutie: {2}
Scot 2
4 submultimi = 22, generate in ordine: {}, {1}, {1,2}, {2}.
Ingredientele algoritmului:
- sol — lista cu elementele alese pana acum (submultimea in constructie)
- back(start) — genereaza toate extensiile posibile cu elemente ≥ start
- Inregistrare la INCEPUT: inregistram sol inaintea buclei (includem si multimea vida)
- Revenire: dupa explorarea ramurii, scoatem elementul adaugat (sol.pop())
- Parametrul start creste la fiecare nivel, garantand ordine si unicitate
3
3. Implementarea completa in Python
# Generarea submultimilor prin backtracking # Limbaj: Python | Nivel: mat-info cls XI def submultimi_bt(n): sol = [] # submultimea in constructie rezultate = [] def back(start): # inregistram solutia curenta (chiar daca e vida) rezultate.append(sol[:]) for i in range(start, n + 1): sol.append(i) # adaugam i la submultime back(i + 1) # continuam cu elemente > i sol.pop() # revenire: scoatem i back(1) return rezultate # Generam submultimile lui {1, 2, 3} n = 3 subs = submultimi_bt(n) print(f"Submultimile lui {chr(123)}1,...,{n}{chr(125)} ({len(subs)} bucati):") for s in subs: if s: print('{' + ', '.join(map(str, s)) + '}') # nevida else: print('{}') # multimea vida
Output real (rulat cu python):
Submultimile lui {1,...,3} (8 bucati):
{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
Observatie cheie: Ordinea de generare este ordinea arborelui de cautare: mai intai toate submultimile care contin 1, in interiorul lor cele care contin 2, etc. Aceasta este ordinea lexicografica a submultimilor.
4
4. Produs cartezian si conexiunea cu submultimile
Produsul cartezian A1 × A2 × … × Ak este multimea tuturor tuplilor (a1, a2, …, ak) cu ai ∈ Ai. Numarul de elemente este |A1| × |A2| × … × |Ak|.
# Produs cartezian al k multimi prin backtracking def produs_cartezian_bt(multimi): k = len(multimi) sol = [None] * k # tuplul in constructie rezultate = [] def back(nivel): if nivel == k: # tuplul e complet rezultate.append(tuple(sol)) return for elem in multimi[nivel]: sol[nivel] = elem back(nivel + 1) back(0) return rezultate multimi = [[1, 2], [3, 4], [5, 6]] rez = produs_cartezian_bt(multimi) print(f"Produs cartezian {{1,2}} x {{3,4}} x {{5,6}} (2x2x2={len(rez)} tupli):") for r in rez: print(r)
Output real (rulat cu python):
Produs cartezian {1,2} x {3,4} x {5,6} (2x2x2=8 tupli):
(1, 3, 5)
(1, 3, 6)
(1, 4, 5)
(1, 4, 6)
(2, 3, 5)
(2, 3, 6)
(2, 4, 5)
(2, 4, 6)
Conexiunea cu submultimile: Generarea submultimilor lui {1,...,n} este echivalenta cu generarea produsului cartezian {0,1}n, unde 0 = nu includem si 1 = includem. De exemplu, (1,0,1) corespunde submultimii {1,3}.
Diferenta intre produs cartezian si submultimi: La produsul cartezian avem k niveluri fixe si fiecare nivel parcurge propria multime. La submultimi, dimensiunea solutiei variaza (de la 0 la n) si parametrul start evita dublurile.
Diferenta intre produs cartezian si submultimi: La produsul cartezian avem k niveluri fixe si fiecare nivel parcurge propria multime. La submultimi, dimensiunea solutiei variaza (de la 0 la n) si parametrul start evita dublurile.
5
5. Submultimi cu restrictii: taieri de ramuri (pruning)
Backtracking-ul devine cu adevarat eficient cand adaugam conditii de taiere (pruning): daca stim ca o ramura nu poate duce la o solutie valida, o eliminam inainte de a o explora complet.
# Submultimi cu suma exacta S (cu pruning) def submultimi_suma(n, S): sol = [] rezultate = [] def back(start, suma_curenta): if suma_curenta == S: rezultate.append(sol[:]) return if suma_curenta > S: return # pruning: suma a depasit S, taiem for i in range(start, n + 1): sol.append(i) back(i + 1, suma_curenta + i) sol.pop() back(1, 0) return rezultate n = 6 S = 7 rez = submultimi_suma(n, S) print(f"Submultimi din {{1,...,{n}}} cu suma={S} ({len(rez)} solutii):") for s in rez: print('{' + ', '.join(map(str, s)) + '}')
Output real (rulat cu python):
Submultimi din {1,...,6} cu suma=7 (4 solutii):
{1, 2, 4}
{1, 6}
{2, 5}
{3, 4}
Din cele 26 = 64 submultimi posibile, backtracking-ul cu pruning exploreaza mult mai putine. Cand suma depaseste 7, intreaga subramura este eliminata. Corectitudinea taierii: elementele sunt pozitive, deci adaugand mai mult suma nu poate scadea — nu pierdem nicio solutie valida.
6
6. Implementare C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul mat-info intensiv, implementam acelasi algoritm in C++. Diferente fata de Python: tablou static int sol[20] cu contor lung in loc de lista dinamica; variabile globale pentru acces direct din recursie; afisare directa.
#include <iostream> using namespace std; int n; int sol[20]; // submultimea in constructie int lung; // numarul de elemente curente in sol void back(int start) { // afisam solutia curenta (inclusiv {}) cout << "{"; for (int i = 0; i < lung; i++) { if (i > 0) cout << ", "; cout << sol[i]; } cout << "}\n"; for (int i = start; i <= n; i++) { sol[lung++] = i; // adaugam i, lung creste back(i + 1); // continuam cu elemente > i lung--; // revenire: lung scade } } int main() { n = 3; lung = 0; cout << "Submultimile lui {1,...," << n << "} (2^n=" << (1 << n) << " bucati):\n"; back(1); return 0; }
Output real (compilat g++ -std=c++17, apoi rulat):
Submultimile lui {1,...,3} (2^n=8 bucati):
{}
{1}
{1, 2}
{1, 2, 3}
{1, 3}
{2}
{2, 3}
{3}
Tehnica sol[lung++] si lung--: Tabloul sol joaca rolul stivei. lung este numarul de elemente curente. sol[lung++] = i pune i pe varf si incrementeaza (echivalent sol.append(i) in Python), iar lung-- elimina ultimul element (echivalent sol.pop()). Acelasi output ca versiunea Python — algoritmul este identic, doar sintaxa difera.