Generarea combinărilor

O combinare de $k$ elemente din $n$ valori distincte alege $k$ valori fără repetiție, iar ordinea nu contează. Din $\{1,2,3\}$, combinările de lungime 2 sunt $\{1,2\}$, $\{1,3\}$ și $\{2,3\}$. Pentru a nu genera și 21 după 12, construim valorile în ordine strict crescătoare.

O combinare de $n$ elemente luate câte $k$ este o submulțime cu $k$ elemente: ordinea nu contează, iar elementele sunt distincte. Numărul lor este $C_n^k=\frac{n!}{k!(n-k)!}$; pentru $n=3$ și $k=2$ sunt 3. Pentru a genera fiecare combinare o singură dată, soluția se construiește ca un vector strict crescător: la fiecare poziție se aleg numai valori mai mari decât cea precedentă. Astfel $\{1,2\}$ apare o dată, ca 12, nu și ca 21. Invariantul este $x_1<x_2<\dots <x_p$ pentru primele $p$ poziții completate. Pentru $k=0$ există o singură combinare, cea vidă; pentru $k=n$ există o singură combinare, mulțimea întreagă. Se poate tăia o parte din ramuri limitând valorile: la poziția $p$ este nevoie de $k-p$ valori ulterioare, deci $c\le n-(k-p)$ (cu pozițiile numerotate de la 1 la $k$).

Exemplul 1 — combinările de 2 din $\{1,2,3\}$.

#include <iostream>
using namespace std;
int x[3];
void gen(int poz, int inceput) {
    if (poz == 2) {
        cout << x[0] << x[1] << " ";
        return;
    }
    for (int c = inceput; c <= 3; ++c) {
        x[poz] = c;
        gen(poz + 1, c + 1);
    }
}
int main() {
    gen(0, 1);
    return 0;
}

Programul afișează 12 13 23 . Apelul gen(0, 1) alege mai întâi 1; gen(1, 2) completează cu 2 și apoi cu 3, obținând 12 și 13. Revenind la prima poziție, alege 2 și completează cu 3, obținând 23. Ramura care începe cu 3 nu mai are o valoare mai mare disponibilă și nu afișează nimic. Astfel fiecare selecție de două elemente apare o singură dată.

Exemplul 2 — combinările de 2 din $\{1,2,3,4\}$. Se obțin $C_4^2=6$ combinări, în ordinea 12 13 14 23 24 34. Dintre ele, cele cu suma elementelor 5 sunt 14 și 23. Dacă se cer combinările de 3 din $\{1,2,3,4,5\}$ cu suma 9, se testează suma la sfârșit sau pe parcurs: sunt $C_5^3=10$ combinări în total, iar suma 9 o au 135 și 234, adică 2 dintre ele.

Exemplul 3 — relații între numere de combinări. Numărul combinărilor respectă relațiile $C_n^k=C_n^{n-k}$ și $C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$. Pentru $n=4$ și $k=2$: $C_4^2=C_3^1+C_3^2=3+3=6$, în acord cu lista 12 13 14 23 24 34; pentru $n=5$: $C_5^3=C_5^2=10$. A doua relație are o interpretare directă: combinările care conțin elementul $n$ sunt $C_{n-1}^{k-1}$, iar cele care nu îl conțin sunt $C_{n-1}^k$. Dacă generarea nu ar impune ordinea crescătoare, din $\{1,2,3\}$ s-ar obține 6 șiruri de 2 elemente în loc de 3 combinări.

Exemplul 4 — legătura cu aranjamentele. Fiecare combinare de $k$ elemente se poate ordona în $k!$ moduri, deci $A_n^k=C_n^k\cdot k!$. Pentru $n=4$ și $k=2$: $A_4^2=12$, $C_4^2=6$ și $2!=2$, adică $12=6\cdot 2$. Memoria de lucru pentru soluția curentă și apelurile recursive este proporțională cu $k$; scrierea tuturor rezultatelor cere cel puțin $k\cdot C_n^k$ pași.

Exemplul 5 — tăierea ramurilor fără destule valori. Pentru combinările de 3 din $\{1,2,3,4\}$, rezultatul este 123 124 134 234, adică $C_4^3=4$ combinări. Fără limită superioară, generarea face 15 apeluri ale funcției gen, deoarece încearcă și prefixe care nu se mai pot completa, cum sunt 3 sau 14. Dacă ciclul se oprește la $c\le n-(k-1-poz)$, cu pozițiile numerotate de la 0, prima poziție primește doar 1 sau 2, a doua doar valori până la 3, iar apelurile scad la 10. Cele patru combinări rămân aceleași: limita taie doar ramuri fără soluții.

Nu confunda combinările cu aranjamentele. Fiecare mulțime de $k$ elemente are $k!$ ordonări când elementele sunt distincte; de aceea $A_n^k=C_n^{k}k!$. Pentru a număra combinările cu o proprietate, generează mulțimile în ordine crescătoare și verifică proprietatea pe fiecare. O limită superioară mai strânsă pentru valorile încercate poate evita ramuri care nu mai au destule valori pentru completare, dar nu schimbă mulțimea soluțiilor. La numărare, folosește simetria $C_n^k=C_n^{n-k}$: alegerea celor $k$ elemente păstrate este echivalentă cu alegerea celor $n-k$ elemente excluse, deci $C_6^4=C_6^2=15$. Într-un program, verifică lungimea soluției: la generarea combinărilor de $k$ elemente, afișarea apare când s-au completat exact $k$ poziții, nu $n$. Dacă o combinare trebuie să conțină un element dat, acesta se fixează și se aleg celelalte $k-1$ elemente dintre cele $n-1$ rămase: $C_{n-1}^{k-1}$ posibilități, de pildă $C_4^2=6$ combinări de 3 elemente din $\{1,\dots ,5\}$ care conțin elementul 1.

Exemplu în formatul examenului. Câte submulțimi cu 3 elemente ale mulțimii $\{1,2,3,4,5\}$ au suma elementelor egală cu 9?

• a) 1
• b) 2
• c) 3
• d) 10

Răspunsul corect este b). Submulțimile cu 3 elemente sunt $C_5^3=10$. Suma 9 o au $\{1,3,5\}$ și $\{2,3,4\}$; celelalte au suma diferită, de pildă $\{1,2,3\}$ are 6, $\{1,4,5\}$ are 10, iar $\{2,3,5\}$ are 10. Deci sunt 2 astfel de submulțimi. Varianta d) este numărul tuturor combinărilor, fără condiția pe sumă.

Greșeli frecvente

• Greșit: 12 și 21 sunt combinări diferite.
  Corect: la combinări ordinea nu contează, deci reprezintă aceeași mulțime.
• Greșit: combinările pot fi generate fără restricția de ordine crescătoare, fiindcă duplicatele se elimină la final.
  Corect: restricția de ordine evită generarea duplicatelor.
• Greșit: $C_n^k=A_n^k$.
  Corect: $C_n^k=A_n^k/k!$.

Înainte și după