Capitolul 15 · Lecția 15.2 din 2

Generarea submulțimilor și numărarea soluțiilor

Vectorul caracteristic, ordinea generării și formulele de numărare cerute la grile.

Capitolul 15: Backtracking și GreedyConținut verificat

Pe scurt pentru BAC · 5 idei

O submulțime a lui {1..n} se codifică printr-un șir de n biți, unde bitul i spune dacă elementul i apare (1) sau nu (0).
Submulțimile nevide sunt $2^n - 1$ , cele cu exact k elemente sunt $C_n^k$ , iar permutările sunt $n!$ .
Submulțimea {1,3} pentru n=3 are biții 101, deci e a 6-a generată, numărând de la mulțimea vidă.
Submulțimile cu cel puțin 2 elemente ale lui {1,2,3,4} sunt $2^4 - 1 - C_4^1 = 16 - 1 - 4 = 11$ .
Grilele cer de obicei numărul de soluții, a k-a soluție sau vecina ei, toate rezolvabile cu ordinea lexicografică, fără să rulezi programul.

Pe această pagină5 secțiuni

Vectorul caracteristic

O submulțime a mulțimii {1..n} = un șir de n biți: bitul i spune dacă elementul i APARE (1) sau NU (0).

Pentru n = 3, cele $2^3 = 8$ submulțimi, în ordinea numărării binare:

biți	submulțimea
000	∅
001	{3}
010	{2}
011	{2,3}
100	{1}
101	{1,3}
110	{1,2}
111	{1,2,3}

Formulele de numărare (setul complet de grile)

submulțimi ale unei mulțimi cu n elemente: $2^n$ (cu tot cu ∅);
submulțimi NEVIDE: $2^n - 1$ ;
submulțimi cu EXACT k elemente: $C_n^k$ ;
cuvinte de lungime k din n simboluri (cu repetiție): $n^k$ ;
permutări: $n!$ ; aranjamente: $A_n^k$ .

Exemplu. Câte submulțimi cu cel puțin 2 elemente are {1,2,3,4}? $2^4 - 1 - C_4^1 = 16 - 1 - 4 = 11$ .

"A câta soluție este...?" (tiparul de subiect)

Generarea pe vector caracteristic urmează NUMĂRAREA BINARĂ: submulțimea {1,3} pentru n=3 are biții 101 = 5 în binar → e a 6-a generată (numărând de la ∅ = prima). Invers: a 7-a soluție are indicele 6 = 110 → {1,2}.

Backtracking pe subprograme (recunoaștere)

Schema generică: la pasul k alegi o valoare validă, avansezi; când nu mai există valori, REVII la pasul k-1. Grilele cer de obicei doar: numărul de soluții, a k-a soluție, sau soluția anterioară/următoare uneia date: toate rezolvabile cu ordinea lexicografică, fără a "rula" programul.

Exemplu. Permutările lui {1,2,3} în ordine: 123, 132, 213, 231, 312, 321. Anterioara lui 312? → 231 ✓.

Reține

Submulțimi = numărare binară pe vector caracteristic; 2^n totale. La "a k-a soluție", scrie k-1 în binar pe n biți. Permutările merg lexicografic, ca în dicționar.

Greșeli frecvente

∅ se numără printre submulțimi: totalul e 2^n, nu 2^n - 1.
Corespondența soluție ↔ index: a k-a soluție are reprezentarea k-1 (numărarea începe de la 0).
La permutări, următoarea lexicografică nu e "rotire": compară poziție cu poziție.

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int n = 3, st[10];

void back(int k) {
    if (k > n) {
        cout << "{";
        for (int i = 1; i <= n; i++)
            if (st[i]) cout << i;
        cout << "} ";
        return;
    }
    for (int v = 0; v <= 1; v++) {
        st[k] = v;
        back(k + 1);
    }
}

int main() {
    back(1);
    return 0;
}