Generarea partițiilor unei mulțimi

Descrierea algoritmului

O partiție a mulțimii A este o familie de submulțimi ale lui A, numite și clase, care îndeplinesc condițiile:

• fiecare submulțime este nevidă;
• oricare două submulțimi sunt disjuncte;
• reuniunea tuturor submulțimilor este A.

Ordinea submulțimilor și ordinea elementelor dintr-o submulțime nu contează.

Partițiile se generează prin metoda backtracking. Elementele mulțimii A = {a₁, a₂, …, aₙ} se repartizează pe submulțimi în ordinea indicilor. Soluția se memorează într-un vector st, în care st[k] este numărul submulțimii în care intră elementul aₖ.

Aceeași partiție poate fi scrisă cu mai multe numerotări ale submulțimilor. Pentru ca fiecare partiție să fie generată o singură dată, submulțimile se numerotează în ordinea în care apar:

• elementul a₁ intră întotdeauna în submulțimea 1;
• elementul aₖ intră fie într-o submulțime deja folosită de elementele a₁, …, aₖ₋₁, fie în prima submulțime nouă.

Valorile posibile pe nivelul k sunt deci 1, 2, …, m + 1, unde m este maximul valorilor st[1], …, st[k−1], adică numărul submulțimilor folosite până atunci.

Etapele algoritmului sunt următoarele:

1. Se pornește de la nivelul 1, cu st[1] = 0.
2. Pe nivelul curent k, valoarea st[k] se mărește cu 1, dacă este mai mică decât m + 1.
3. Dacă nivelul curent este n, vectorul st descrie o partiție completă, care se afișează: submulțimea c este formată din elementele aᵢ pentru care st[i] = c.
4. Dacă nivelul curent este mai mic decât n, se trece la nivelul k + 1, iar st[k + 1] primește valoarea 0.
5. Dacă pe nivelul k nu mai există nicio valoare de încercat, se revine la nivelul k − 1, care continuă cu valoarea următoare.
6. Algoritmul se încheie când se revine sub nivelul 1.

Orice valoare aleasă din intervalul de mai sus dă o repartizare corectă, deci condiția de continuare este întotdeauna adevărată. Restricția privind numerotarea submulțimilor este cuprinsă în limita valorilor încercate.

Exemplificarea etapelor

Se consideră mulțimea A = {2, 5, 7, 9}, cu a₁ = 2, a₂ = 5, a₃ = 7 și a₄ = 9. Algoritmul generează partițiile în ordinea următoare:

Trecerea de la partiția 1 la partiția 2 arată cum se lucrează pe ultimul nivel. După st = 1 1 1 1, pe nivelul 4 maximul valorilor anterioare este 1, deci se mai poate încerca valoarea 2: elementul 9 trece într-o submulțime nouă. Valoarea 3 nu mai este permisă pe nivelul 4, fiindcă înaintea lui s-a folosit o singură submulțime.

Trecerea de la partiția 5 la partiția 6 arată revenirea. După st = 1 1 2 3, nivelul 4 nu mai are valori, iar nivelul 3 nu mai are nici el, fiindcă înaintea lui s-a folosit o singură submulțime și valoarea 2 a fost deja încercată. Se revine pe nivelul 2, unde st[2] crește de la 1 la 2: elementul 5 trece în submulțimea a doua. Nivelurile 3 și 4 se completează apoi de la valoarea 1.

Pe nivelul 4 se încearcă valorile 1, 2, 3 atunci când înaintea lui s-au folosit două submulțimi, dar valorile 1, 2, 3, 4 atunci când s-au folosit trei. Numărul valorilor încercate diferă deci de la o ramură la alta. Mulțimea cu patru elemente are 15 partiții.

Aprecierea complexității

Numărul partițiilor unei mulțimi cu n elemente este numărul lui Bell, B(n): B(4) = 15, B(5) = 52, B(10) = 115 975. Algoritmul generează fiecare partiție o singură dată, deci timpul de executare este cel puțin proporțional cu B(n).

Fiecare partiție se obține după n niveluri, iar la fiecare încercare se calculează maximul valorilor de pe nivelurile anterioare, cu cel mult n comparații. Timpul de executare este deci cel mult de ordinul n² · B(n). Numărul lui Bell crește mai repede decât 2ⁿ, deci algoritmul are complexitate exponențială și poate fi folosit numai pentru mulțimi cu un număr mic de elemente.

Problema propusă

Enunț. Se citesc de la tastatură un număr natural n (2 ≤ n ≤ 10) și apoi n numere naturale nenule, distincte. Se cere să se afișeze toate modurile în care numerele citite pot fi împărțite în cel puțin două grupe, astfel încât suma numerelor din fiecare grupă să fie aceeași. Fiecare împărțire se afișează pe câte o linie, cu grupele scrise între acolade. Dacă nu există nicio astfel de împărțire, se afișează mesajul nu exista.

Exemplu: pentru n = 6 și numerele 1 2 3 5 6 7 se afișează:

{1,2,3,6} {5,7}
{1,5,6} {2,3,7}
{1,7} {2,6} {3,5}

Descrierea soluției. O împărțire a numerelor în grupe este o partiție a mulțimii numerelor citite, deci se generează toate partițiile prin algoritmul descris mai sus. Numerele se memorează în vectorul a, iar st[i] este grupa în care intră a[i].

Pentru fiecare partiție completă se calculează suma fiecărei grupe, într-un vector suma, unde suma[g] adună numerele a[i] cu st[i] = g. Numărul grupelor este cea mai mare valoare din st. Partiția se afișează numai dacă are cel puțin două grupe și toate sumele sunt egale cu suma[1]. Un contor numără partițiile afișate; dacă la sfârșit el are valoarea 0, se afișează mesajul nu exista.

Implementarea soluției.

#include <iostream>
using namespace std;

int a[11], st[11];
int n, k, as, ev, nrSolutii;

void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

void init() {
    st[k] = 0;
}

int succesor() {
    int maxim = 0;
    for (int i = 1; i < k; i++)
        if (st[i] > maxim)
            maxim = st[i];          // numarul grupelor folosite pana acum

    if (st[k] < maxim + 1) {
        st[k]++;
        return 1;
    }
    return 0;
}

int valid() {
    return 1;
}

int solutie() {
    return k == n;
}

/* Afiseaza partitia numai daca are cel putin doua grupe,
   toate cu aceeasi suma. */
void tipar() {
    int nrGrupe = 0;
    int suma[11] = {0};
    for (int i = 1; i <= n; i++) {
        suma[st[i]] += a[i];
        if (st[i] > nrGrupe)
            nrGrupe = st[i];
    }

    if (nrGrupe < 2)
        return;
    for (int g = 2; g <= nrGrupe; g++)
        if (suma[g] != suma[1])
            return;

    nrSolutii++;
    for (int g = 1; g <= nrGrupe; g++) {
        cout << "{";
        int primul = 1;
        for (int i = 1; i <= n; i++)
            if (st[i] == g) {
                if (!primul)
                    cout << ",";
                cout << a[i];
                primul = 0;
            }
        cout << "} ";
    }
    cout << endl;
}

void bt() {
    k = 1;
    init();
    while (k > 0) {
        as = 1;
        ev = 0;
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }
        if (as)
            if (solutie())
                tipar();
            else {
                k++;
                init();
            }
        else
            k--;
    }
}

int main() {
    citire();
    bt();
    if (nrSolutii == 0)
        cout << "nu exista";
    return 0;
}

Pentru exemplul din enunț, suma tuturor numerelor este 24. Partițiile afișate au două grupe cu suma 12, respectiv trei grupe cu suma 8. Pentru numerele 1 2 4 8 nu există nicio împărțire, fiindcă cel mai mare număr este mai mare decât suma celorlalte, și se afișează nu exista.