Generarea submulțimilor

O submulțime a unei mulțimi de $n$ elemente se obține alegând, pentru fiecare element, dacă îl includem sau nu. Pentru $\{1,2\}$, rezultatele sunt $\varnothing$, $\{1\}$, $\{2\}$ și $\{1,2\}$. Sunt $2^n$ submulțimi, inclusiv cea vidă și mulțimea întreagă.

O mulțime cu $n$ elemente are $2^n$ submulțimi: pentru fiecare element există două alegeri independente, să fie inclus sau nu. Submulțimea vidă și mulțimea întreagă sunt incluse. O submulțime se reprezintă printr-un vector caracteristic $x_1,\dots ,x_n$, cu $x_i=1$ dacă elementul $i$ este ales și $x_i=0$ altfel. Generarea prin backtracking parcurge pe fiecare nivel cele două valori, 0 și 1, fără alte condiții. Dacă 0 este încercat înaintea lui 1, ordinea de generare pentru $\{1,2\}$ este: mulțimea vidă, $\{2\}$, $\{1\}$, $\{1,2\}$. Numărul submulțimilor cu exact $k$ elemente este $C_n^k$, iar suma numerelor lor este ${\sum }_{k=0}^n{C}_n^k=2^n$.

Exemplul 1 — submulțimile lui $\{1,2\}$.

#include <iostream>
using namespace std;
int x[10], n = 2;
void bt(int k) {
    if (k > n) {
        cout << "{";
        for (int i = 1; i <= n; ++i)
            if (x[i]) cout << i << " ";
        cout << "} ";
        return;
    }
    for (int v = 0; v <= 1; ++v) {
        x[k] = v;
        bt(k + 1);
    }
}
int main() {
    bt(1);
    return 0;
}

Programul afișează {} {2 } {1 } {1 2 } , adică $2^2=4$ submulțimi. Fiecare soluție completă corespunde unui vector caracteristic: 00, 01, 10, 11. Dacă se modifică valoarea lui $n$ în 3, programul afișează $2^3=8$ submulțimi. Ordinea provine din ordinea candidaților: pe fiecare nivel se încearcă întâi 0 („nu aleg”), apoi 1 („aleg”), iar ultimul nivel se schimbă cel mai des. Pentru ca elementul 1 să apară primul în ieșire, ordinea candidaților ar trebui inversată. Fiecare nivel are exact două ramuri, deci arborele apelurilor este un arbore binar complet cu $n+1$ niveluri și $2^n$ frunze.

Exemplul 2 — submulțimi cu o proprietate. Pentru $\{1,2,3\}$ cele 8 submulțimi au sumele $0,3,2,5,1,4,3,6$ în ordinea vectorilor caracteristici $000,001,010,011,100,101,110,111$ (cu $x_1$ primul bit din stânga). Singura submulțime cu suma 4 este $\{1,3\}$. Pentru a număra submulțimile fără două elemente consecutive din $\{1,2,3,4\}$ se adaugă condiția de continuare „dacă $x_{k-1}=1$, atunci $x_k$ nu poate fi 1”: rezultă 8 submulțimi (vida, cele 4 cu un element, $\{1,3\}$, $\{1,4\}$ și $\{2,4\}$), mai puține decât cele $2^4=16$ posibile. Numărul lor, 8, este un număr din șirul lui Fibonacci.

Exemplul 3 — câte ori apare fiecare element. Un element oarecare apare în exact $2^{n-1}$ dintre cele $2^n$ submulțimi, adică în jumătate dintre ele: celelalte $n-1$ elemente pot fi alese liber. Pentru $\{1,2,3\}$ fiecare element apare în $4$ submulțimi, deci suma tuturor sumelor este $(1+2+3)\cdot 4=24$, ceea ce coincide cu $0+3+2+5+1+4+3+6=24$. O astfel de verificare prin formulă confirmă rezultatul unui program fără a lista submulțimile.

Exemplul 4 — alt mod de generare. Un număr întreg de la 0 la $2^n-1$ scris în baza 2 cu $n$ cifre este un vector caracteristic. Pentru $n=3$, numerele 0, 1, ..., 7 reprezintă toate cele 8 submulțimi; submulțimea corespunzătoare lui 5 ($101_2$) conține elementele de pe pozițiile cu bitul 1. Metoda cere $O(n)$ operații pentru fiecare submulțime.

Exemplul 5 — submulțimile cu exact $k$ elemente. Pentru $n=4$ și $k=2$ se păstrează doar vectorii caracteristici cu exact doi de 1: 0011, 0101, 0110, 1001, 1010, 1100. Ei corespund submulțimilor $\{3,4\}$, $\{2,4\}$, $\{2,3\}$, $\{1,4\}$, $\{1,3\}$ și $\{1,2\}$, în total $C_4^2=6$. Cele cinci valori ale lui $k$ dau $1+4+6+4+1=16=2^4$ submulțimi. În backtracking se ține un contor al elementelor alese și se abandonează ramura în care el depășește $k$.

Fiecare element are două alegeri independente, de unde $2^n$. Dacă se cer doar submulțimile cu exact $k$ elemente, numărul este $C_n^k$. Ordinea afișării depinde de metoda de generare și nu face parte din definiția mulțimii. Nu număra de două ori aceeași mulțime scrisă în altă ordine: $\{1,2\}$ și $\{2,1\}$ coincid. Dacă enunțul exclude submulțimea vidă, scade 1 din $2^n$; dacă exclude și mulțimea întreagă, scade 2. Pentru $n=4$ rezultă 15, respectiv 14 submulțimi. Submulțimile care conțin un element dat sunt $2^{n-1}$, iar cele care conțin două elemente date sunt $2^{n-2}$; pentru $\{1,2,3,4\}$ cele care conțin 1 și 2 sunt $2^2=4$. La o restricție de tipul „nu există două elemente consecutive”, numărul crește ca în șirul lui Fibonacci: 2, 3, 5, 8 pentru $n=1,2,3,4$.

Exemplu în formatul examenului. Câte submulțimi ale mulțimii $\{1,2,3,4\}$ nu conțin două elemente consecutive (numere care diferă prin 1)? Se numără și submulțimea vidă.

• a) 5
• b) 8
• c) 12
• d) 16

Răspunsul corect este b). Submulțimile fără elemente consecutive sunt: vida; cele patru cu un singur element, $\{1\},\{2\},\{3\},\{4\}$; și cele cu două elemente neconsecutive, $\{1,3\}$, $\{1,4\}$ și $\{2,4\}$. Nu există submulțimi cu trei elemente care să respecte condiția. Total $1+4+3=8$. Varianta d) numără toate cele $2^4=16$ submulțimi, fără restricție.

Greșeli frecvente

• Greșit: o mulțime cu $n$ elemente are $n^2$ submulțimi.
  Corect: are $2^n$.
• Greșit: submulțimea vidă nu se numără.
  Corect: este o submulțime și apare printre cele $2^n$.
• Greșit: $\{1,2\}$ și $\{2,1\}$ sunt submulțimi diferite.
  Corect: sunt aceeași mulțime.

Înainte și după