Generarea combinărilor

Combinările de n elemente luate câte k sunt submulțimile cu k elemente ale unei mulțimi cu n elemente. Într-o submulțime nu contează ordinea elementelor, așa că {1, 2, 3} și {3, 1, 2} sunt una și aceeași combinare. Numărul lor este C(n,k) = n! / (k!·(n−k)!).

Se lucrează pe mulțimea {1, 2, …, n}; dacă elementele sunt de altă natură, se generează combinările indicilor, iar valorile se citesc după aceea din vectorul care le păstrează.

Descrierea algoritmului în limbaj natural

Combinările se generează prin metoda backtracking. Soluția se construiește într-un vector st, cu k poziții, numite niveluri: pe nivelul i se așază al i-lea element al combinării.

Cum se evită repetarea aceleiași submulțimi. Fiindcă ordinea nu contează, se impune ca elementele să fie așezate în ordine strict crescătoare: valoarea de pe nivelul i trebuie să fie mai mare decât cea de pe nivelul i−1. Astfel, din toate ordonările posibile ale unei submulțimi se generează una singură, cea crescătoare.

Extinderea unei soluții parțiale. Când nivelurile 1, 2, …, i−1 sunt completate, pe nivelul i se încearcă, pe rând, valorile de la st[i−1] + 1 în sus. O valoare este acceptată dacă mai rămân destule valori pentru nivelurile care urmează: pe nivelul i nu are rost să se pună o valoare mai mare decât n − k + i, fiindcă după ea nu ar mai încăpea cele k − i elemente rămase. La primul nivel valorile se încearcă începând de la 1.

Dacă valoarea încercată este acceptată, se trece pe nivelul următor și se reia încercarea acolo. Când s-a completat și nivelul k, în vector se află o combinare completă, care se afișează.

Trecerea de la o soluție la următoarea. După afișarea unei combinări nu se pornește de la capăt: se rămâne pe nivelul k și se încearcă valoarea imediat următoare celei tocmai folosite. Dacă pe nivelul k s-au epuizat valorile — adică s-a depășit n — se coboară pe nivelul k−1 și se încearcă acolo valoarea următoare, apoi se reia completarea nivelurilor de deasupra. Acest pas înapoi este revenirea (backtracking) propriu-zisă.

Algoritmul se încheie când s-au epuizat valorile de pe primul nivel.

Exemplificarea etapelor

Se generează combinările de 3 elemente ale mulțimii {1, 2, 3, 4, 5}, deci n = 5 și k = 3. Limita superioară pentru nivelul i este n − k + i, adică 3 pentru nivelul 1, 4 pentru nivelul 2 și 5 pentru nivelul 3.

Primele cinci combinări obținute sunt, în ordine: 1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5.

Se vede aici și rolul limitei superioare: la pasul 6, pe nivelul 2 s-ar putea încerca și valoarea 5, dar 5 depășește limita n − k + 2 = 4, fiindcă după ea nu ar mai rămâne nicio valoare pentru nivelul 3. Fără această limită algoritmul ar încerca și ar respinge astfel de drumuri, fără să greșească rezultatul, dar cu pași în plus.

Aprecierea complexității

Numărul combinărilor generate este C(n,k), iar fiecare este afișată în k pași, așa că timpul de executare este de ordinul k·C(n,k). La aceasta se adaugă încercările care nu duc la o soluție completă, dar numărul lor rămâne de același ordin.

Complexitatea nu este polinomială: pentru k apropiat de n/2, C(n,k) crește exponențial în raport cu n. Pentru n = 20 și k = 10 se generează 184 756 de combinări, iar pentru n = 30 și k = 15 numărul lor trece de 155 de milioane. De aceea generarea tuturor combinărilor se folosește numai pentru valori mici ale lui n, iar acolo unde se cere doar una dintre ele — cea optimă, de pildă — se caută metode care nu le enumeră pe toate.

Problema propusă

Enunț. Într-o clasă sunt n elevi (3 ≤ n ≤ 20), numerotați de la 1 la n, iar pentru fiecare se cunoaște punctajul obținut la un test, număr natural. Se formează o echipă de k elevi. Se cere să se afișeze toate echipele posibile al căror punctaj total este exact S, fiecare echipă pe câte o linie, prin numerele de ordine ale elevilor care o compun, în ordine crescătoare.

Exemplu: pentru n = 5, k = 3, S = 12 și punctajele 3, 4, 5, 2, 6 se afișează 1 2 3, fiindcă 3 + 4 + 5 = 12, și 2 4 5, fiindcă 4 + 2 + 6 = 12.

Descrierea soluției în limbaj natural. Echipa este o submulțime de k elevi dintr-o mulțime de n, iar ordinea în care sunt scriși membrii ei nu are importanță, deci fiecare echipă posibilă este o combinare de n luate câte k. Se generează, prin algoritmul de mai sus, toate combinările indicilor elevilor.

De fiecare dată când se completează nivelul k, adică s-a obținut o echipă întreagă, se adună punctajele celor k elevi din vectorul de punctaje, folosind numerele de ordine aflate în vectorul soluție. Dacă suma obținută este egală cu S, echipa se afișează; altfel se trece mai departe, fără să se întrerupă generarea.

Verificarea se face abia la nivelul k, când echipa este completă, fiindcă o sumă parțială mai mică decât S nu spune nimic: elevii care urmează pot aduce exact cât lipsește.

Implementarea soluției.

#include <iostream>
using namespace std;

int p[21];        // punctajele elevilor
int st[21];       // vectorul solutie: st[i] este al i-lea elev din echipa
int n, k, S;

void afiseazaDacaSePotriveste() {
    int suma = 0;
    for (int i = 1; i <= k; i++)
        suma = suma + p[st[i]];

    if (suma == S) {
        for (int i = 1; i <= k; i++)
            cout << st[i] << " ";
        cout << endl;
    }
}

/* Completeaza nivelul i al vectorului solutie. Pe nivelul i se incearca
   valorile de la st[i-1]+1 pana la n-k+i: peste aceasta limita nu ar mai
   ramane destule valori pentru nivelurile urmatoare. */
void combinari(int i) {
    for (int v = st[i - 1] + 1; v <= n - k + i; v++) {
        st[i] = v;
        if (i == k)
            afiseazaDacaSePotriveste();
        else
            combinari(i + 1);
    }
}

int main() {
    cin >> n >> k >> S;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    st[0] = 0;        // pe primul nivel valorile incep de la 1
    combinari(1);

    return 0;
}

Verificarea pe exemplul din enunț. Pentru n = 5, k = 3, S = 12 și punctajele 3, 4, 5, 2, 6, primele combinări generate și sumele lor sunt:

Se afișează 1 2 3 și 2 4 5.