Invatare Atomica

Aranjamente si combinari prin backtracking

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege diferenta dintre aranjamente si combinari, vei implementa algoritmii de generare prin backtracking (Python si C++) si vei sti sa alegi tehnica potrivita in functie de contextul problemei.

Dupa aceasta lectie vei putea:

  • Sa explici diferenta dintre aranjamente (ordinea conteaza) si combinari (ordinea nu conteaza)
  • Sa calculezi A(n,k) si C(n,k) folosind formulele corecte
  • Sa implementezi generarea aranjamentelor prin backtracking cu vector de folosit
  • Sa implementezi generarea combinarilor prin backtracking cu parametrul start
  • Sa identifici ce structura de backtracking genereaza aranjamente vs combinari
  • Sa aplici algoritmii la probleme practice (podiumuri, echipe, coduri)

Incearca singur!

Provocare mentala:

Ai 3 culori: Rosu, Verde, Albastru. Trebuie sa alegi 2 culori pentru un steag cu doua benzi.

Intrebare 1: Daca banda de sus si cea de jos trebuie sa fie culori diferite (ordinea conteaza), cate steaguri diferite poti face?

Intrebare 2: Daca vrei doar sa alegi 2 culori (fara a conta care e sus si care e jos), cate perechi poti forma?

💡 Ai nevoie de un indiciu?

Cu ordine: (R,V), (R,A), (V,R), (V,A), (A,R), (A,V) = 6 steaguri. Aceasta este notiunea de aranjament.

Fara ordine: {R,V}, {R,A}, {V,A} = 3 perechi. Aceasta este notiunea de combinare.

Observa: 6 = 2 × 3. Fiecare combinare genereaza k! = 2 aranjamente.

1

1. Aranjamente vs. Combinari — diferenta fundamentala

Aranjament A(n,k) — selectie ordonata de k elemente din n elemente distincte. Ordinea conteaza: (1,2) ≠ (2,1).

Combinare C(n,k) — selectie neordonata de k elemente din n elemente distincte. Ordinea nu conteaza: {1,2} = {2,1}.
Exemplu comparativ: n=3, k=2

Aranjamente A(3,2) — selectii de 2 din {1,2,3}, cu ordine:

A(3,2) = (1,2)  (1,3)  (2,1)  (2,3)  (3,1)  (3,2)   → 6 solutii

Combinari C(3,2) — selectii de 2 din {1,2,3}, fara ordine:

C(3,2) = {1,2}  {1,3}  {2,3}                          → 3 solutii

Observatie: A(3,2) = 2! × C(3,2). Fiecare combinare poate fi ordonata in 2! = 2 moduri.

Recunoastere rapida

🏆 Podium olimpic (Aur, Argint, Bronz) din 10 sportivi → Aranjament (pozitia conteaza)

⚽ Echipa de fotbal de 11 din 20 jucatori → Combinare (nu exista ordine intr-o echipa)

🔑 Cod PIN de 4 cifre distincte din {0..9} → Aranjament (1234 ≠ 4321)

2

2. Formulele matematice: A(n,k) si C(n,k)

A(n, k) = n! / (n-k)!
= n × (n-1) × … × (n-k+1)    (produs de k factori descendenti)

C(n, k) = n! / (k! × (n-k)!) = A(n,k) / k!
= A(n,k) impartit la k! (impartim la permutarile interne)
Calcule verificate cu Python:
# Formulele A(n,k) si C(n,k)
import math

n, k = 4, 2
A = math.factorial(n) // math.factorial(n - k)
C = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

print(f"A(4,2) = 4! / (4-2)! = 24 / 2 = {A}")
print(f"C(4,2) = 4! / (2! * 2!) = 24 / 4 = {C}")
Output real (python):
A(4,2) = 4! / (4-2)! = 24 / 2 = 12
C(4,2) = 4! / (2! * 2!) = 24 / 4 = 6
Valori uzuale
n=4, k=2:  A(4,2)= 12   C(4,2)= 6   raport A/C = 2! = 2
n=4, k=3:  A(4,3)= 24   C(4,3)= 4   raport A/C = 3! = 6
n=5, k=2:  A(5,2)= 20   C(5,2)=10   raport A/C = 2! = 2
n=5, k=3:  A(5,3)= 60   C(5,3)=10   raport A/C = 3! = 6
n=6, k=3:  A(6,3)=120   C(6,3)=20   raport A/C = 3! = 6

Raportul A(n,k)/C(n,k) este intotdeauna k!.

3

3. Generarea aranjamentelor prin backtracking (Python)

La fiecare nivel al recursiei, incercam toate elementele din {1..n} care nu sunt deja in stiva (marcate in folosit[]). Cand stiva are k elemente, am gasit o solutie. 
# Generare aranjamente A(3,2) prin backtracking

def aranjamente(n, k, stiva=[], folosit=None, pas=[0]):
    if folosit is None:
        folosit = [False] * (n + 1)
    if len(stiva) == k:          # stiva plina = solutie
        pas[0] += 1
        print(f"  Solutia {pas[0]}: {stiva}")
        return
    for i in range(1, n + 1):
        if not folosit[i]:          # element nefolosit
            folosit[i] = True
            stiva.append(i)
            aranjamente(n, k, stiva, folosit, pas)
            stiva.pop()              # backtrack
            folosit[i] = False       # elibereaza

print("A(3,2) - aranjamente de 2 din {1,2,3}:")
aranjamente(3, 2)
Output real (python):
A(3,2) - aranjamente de 2 din {1,2,3}:
  Solutia 1: [1, 2]
  Solutia 2: [1, 3]
  Solutia 3: [2, 1]
  Solutia 4: [2, 3]
  Solutia 5: [3, 1]
  Solutia 6: [3, 2]
Trasarea executiei (primele 3 ramuri)
nivel 0: incerc i=1 → stiva=[1], folosit[1]=True
  nivel 1: i=1 → BLOCAT (folosit[1]=True)
           i=2 → stiva=[1,2] → SOLUTIA 1: [1,2]
           backtrack: stiva=[1], folosit[2]=False
           i=3 → stiva=[1,3] → SOLUTIA 2: [1,3]
  backtrack: stiva=[], folosit[1]=False
nivel 0: incerc i=2 → stiva=[2]
  nivel 1: i=1 → stiva=[2,1] → SOLUTIA 3: [2,1]
4

4. Generarea combinarilor prin backtracking (Python)

Structura backtracking pentru combinari: nu folosim vector folosit[]. In schimb, adaugam parametrul start care impune ca elementele sa fie alese in ordine strict crescatoare. Aceasta elimina duplicatele ({1,2} si {2,1} sunt acelasi lucru). 
# Generare combinari C(3,2) prin backtracking

def combinari(n, k, start=1, stiva=[]):
    if len(stiva) == k:           # stiva plina = solutie
        print(f"  {stiva}")
        return
    for i in range(start, n + 1):  # incepem de la start
        stiva.append(i)
        combinari(n, k, i + 1, stiva)  # urmatorul e strict mai mare
        stiva.pop()

print("C(3,2) - combinari de 2 din {1,2,3}:")
combinari(3, 2)
Output real (python):
C(3,2) - combinari de 2 din {1,2,3}:
  [1, 2]
  [1, 3]
  [2, 3]
De ce lipsesc [2,1], [3,1], [3,2]?

Parametrul start impune alegerea in ordine strict crescatoare. Cand am ales deja 1, urmatorul element incepe de la 2 — deci nu putem reveni la 1. Astfel {1,2} si {2,1} sunt tratate ca un singur obiect, reprezentat intotdeauna ca [1,2].

Comparatie structurala:
Aranjamente: for i in range(1, n+1): if not folosit[i]: ...   (cu vector folosit)
Combinari:    for i in range(start, n+1): ...   (fara vector folosit, start creste)
5

5. Aplicatie: echipe de fotbal — C(5,3)

Problema: Din 5 jucatori, cate echipe de 3?

Ordinea nu conteaza: echipa {1,2,3} este aceeasi indiferent de ordine. Folosim combinari C(5,3) = 10.

# C(5,3) - echipe de 3 din 5 jucatori
import math
n, k = 5, 3
c = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
print(f"Din {n} jucatori, echipe de {k}: C({n},{k}) = {c}")

def combinari(n, k, start=1, stiva=[]):
    if len(stiva) == k:
        print(f"  Echipa: {stiva}")
        return
    for i in range(start, n + 1):
        stiva.append(i)
        combinari(n, k, i + 1, stiva)
        stiva.pop()

print("Echipele posibile:")
combinari(5, 3)
Output real (python):
Din 5 jucatori, echipe de 3: C(5,3) = 10
Echipele posibile:
  Echipa: [1, 2, 3]
  Echipa: [1, 2, 4]
  Echipa: [1, 2, 5]
  Echipa: [1, 3, 4]
  Echipa: [1, 3, 5]
  Echipa: [1, 4, 5]
  Echipa: [2, 3, 4]
  Echipa: [2, 3, 5]
  Echipa: [2, 4, 5]
  Echipa: [3, 4, 5]
Comparatie: podiumuri din aceiasi 5 sportivi

Podiumurile (Aur, Argint, Bronz) sunt aranjamente: A(5,3) = 5 × 4 × 3 = 60, adica de 3! = 6 ori mai multe decat echipele (C(5,3) = 10). Fiecare echipa {1,2,3} genereaza 6 podiumuri distincte: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

6

6. Implementare C++ EXCLUSIV INTENSIV

⚡ Sectiune exclusiv pentru intensiv informatica

In C++, algoritmii sunt identici ca logica cu Python, dar cu sintaxa specifica: tablouri in loc de liste, variabile globale pentru stiva/folosit (practica uzuala la olimpiade). Complexitate timp: O(A(n,k)×k) pentru aranjamente, O(C(n,k)×k) pentru combinari.

Aranjamente A(4,2) in C++:

#include <iostream>
using namespace std;

int n = 4, k = 2;
int stiva[10];
bool folosit[10] = {false};

void aranjamente(int nivel) {
    if (nivel == k) {
        cout << "(";
        for (int i = 0; i < k; i++) {
            cout << stiva[i];
            if (i < k-1) cout << ",";
        }
        cout << ") ";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!folosit[i]) {
            folosit[i] = true;
            stiva[nivel] = i;
            aranjamente(nivel + 1);
            folosit[i] = false;
        }
    }
}

int main() {
    cout << "A(4,2) in C++:" << endl;
    aranjamente(0);
    cout << endl;
    return 0;
}
Output real (g++ -std=c++17, then run):
A(4,2) in C++:
(1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3)

Combinari C(4,2) in C++:

#include <iostream>
using namespace std;

int n = 4, k = 2;
int stiva[10];

void combinari(int nivel, int start) {
    if (nivel == k) {
        cout << "{";
        for (int i = 0; i < k; i++) {
            cout << stiva[i];
            if (i < k-1) cout << ",";
        }
        cout << "} ";
        return;
    }
    for (int i = start; i <= n; i++) {
        stiva[nivel] = i;
        combinari(nivel + 1, i + 1);
    }
}

int main() {
    cout << "C(4,2) in C++:" << endl;
    combinari(0, 1);
    cout << endl;
    return 0;
}
Output real (g++ -std=c++17, then run):
C(4,2) in C++:
{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

Exercitii practice

Exercitiul 1 (Nivel minim) — Calcul si recunoastere

a) Calculeaza A(5,2) si C(5,2) folosind formulele.

b) Identifica tipul selectiei (aranjament sau combinare):
  1. Alegi 2 carti dintr-un pachet de 10 (nu conteaza ordinea)
  2. Formezi un cod de 3 litere distincte din {A,B,C,D,E} (ordinea conteaza)
  3. Alegi 4 membri dintr-un grup de 8 pentru o comisie (nu exista functii diferite)

Exercitiul 2 (Nivel standard) — Modificare algoritm

Modifica algoritmul de aranjamente din lectie astfel incat sa genereze aranjamentele de lungime 3 din multimea ['a','b','c','d']. Afiseaza fiecare aranjament ca un sir (ex: "abc").

Verifica ca obtii A(4,3) = 24 de solutii.

Exercitiul 3 (Nivel performanta) — Combinari cu conditii (pruning)

Genereaza toate combinarile de 3 elemente din {1,2,3,4,5,6} cu suma elementelor cel mult 10.

Indiciu: adauga o conditie de pruning — daca suma stivei curente depaseste deja 10, nu mai continua pe acea ramura.

Raspuns asteptat: 10 solutii din C(6,3)=20.

Ce ai invatat astazi

  • Aranjamente A(n,k): selectie ordonata; A(n,k) = n!/(n-k)!; ordinea conteaza
  • Combinari C(n,k): selectie neordonata; C(n,k) = A(n,k)/k!; ordinea nu conteaza
  • Backtracking aranjamente: vector folosit[] previne reutilizarea elementelor
  • Backtracking combinari: parametrul start impune ordine crescatoare, fara vector folosit
  • Complexitate: O(A(n,k)×k) pentru aranjamente, O(C(n,k)×k) pentru combinari
  • Recunoastere: "ordine conteaza" → aranjament; "ordine nu conteaza" → combinare

Urmatoarea lectie

Continua cu generarea submultimilor si produsul cartezian prin backtracking.

Continua →