Generarea submulțimilor

Problema:

Se dă un număr natural n. Să se genereze toate submulțimile mulțimii {1,2,3,...,n}.

Soluție:

Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare.

Metoda 1

În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente.

• semnificaţia vectorului soluție: x[] reprezintă la un moment dat o submulțime
• condiții externe: x[k] în {1,2,..,n}, k între 1 și n;
• condiții interne: x[k]>x[i], i între 1 și k-1. Deoarece condițiile interne se aplică pentru toate elementele vectorului soluție, este suficient ca x[k]>x[k-1], pentru k>1;
• condiții de existența a soluției: fiecare variantă a vectorului soluție corespunde cu o submulțime. Orice valoare validă plasată în vectorul soluție conduce la o soluție.

void afis(int k){
    for(int i=1 ; i<=k ; ++i)
        cout << x[i] << " ";
    cout << endl;
}
bool valid(int k){
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            afis(k);
            back(k+1);
        }
    }
}

Constatăm că putem rafina condițiile externe; deoarece x[k]>x[k-1], condițiile devin:

• Condiții externe: x[k] în {x[k-1]+1, ... , n}, k între 1 și n. Pentru a uniformiza algoritmul, considerăm de la început că x[0] = 0;
• Condiții interne: nu mai avem condiții interne; funcția valid() nu mai este necesară;
• Condiții de existența a soluției rămân aceleași.

void back(int k){
    for(int i=x[k-1]+1;i<=n;++i)
    {
        x[k]=i;
        afis(k);
        back(k+1);
    }
}

Să observăm că submulțimea vidă nu se regăsește printre soluțiile generate cu acest algoritm. Dacă este cazul, afișarea ei se poate face în afara algoritmului de generare.

Metoda 2

Această metodă se bazează pe observația că pentru fiecare submulțime a mulțimii date, {1,2,...,n} îi corespunde un șir de n biți, notat x[], astfel:

• dacă bitul x[k] = 0, elementul k nu aparține submulțimii curente;
• dacă bitul x[k] = 1, elementul k aparține submulțimii curente.

Reamintim că o mulțime cu n elemente are 2 n submulțimi.

Exemplificăm cu mulțimea {1,2,3,4}.

0	0000	{}	8	1000	{1}
1	0001	{4}	9	1001	{1,4}
2	0010	{3}	10	1010	{1,3}
3	0011	{3,4}	11	1011	{1,3,4}
4	0100	{2}	12	1100	{1,2}
5	0101	{2,4}	13	1101	{1,2,4}
6	0110	{2,3}	14	1110	{1,2,3}
7	0111	{2,3,4}	15	1111	{1,2,3,4}

Putem să generăm toate șirurile de n biți, iar pentru fiecare șir să construim submulțimea corespunzătoare. Generarea șirurilor se poate face în mai multe moduri:

• parcurgem numerele de la 0 la 2n-1 și transformăm fiecare număr în baza 2; obținem astfel pentru fiecare număr un șir de biți care va fi transformat în submulțime;
• generăm direct șirul de biți cerut cu metoda backtracking.

Vom detalia mai jos rezolvarea cu backtracking:

• semnificaţia vectorului soluție: x[] conține la un moment dat un șir de biți care va corespunde unei submulțimi
• condiții externe: x[k] = 0 sau 1;
• condiții interne nu există. Orice configurație parțială a vectorului x[] va conduce la o soluție validă
• condiții de existență a soluției: k == n.

void afis(int k){
    for(int i=1 ; i <= k ; ++i)
        if(x[i] == 1)
            cout << i << " ";
    cout << endl;
}

void back(int k){
    for(int i = 0; i <= 1 ; ++i)
    {
        x[k]=i;
        if(k == n)
            afis(k);
        else
            back(k+1);
    }
}