Modul 03 — Mulțimi & clasa set

Ce e o mulțime — puntea dintre matematică și cod

O mulțime e o colecție în care fiecare element apare O SINGURĂ DATĂ, iar ordinea nu are nicio importanță. O știi de la matematică — acum devine structură de date.

🎯 Unicitate

{3, 7, 3, 5} este de fapt {3, 5, 7} — dublurile dispar AUTOMAT. De-asta mulțimea răspunde instant la „câți distincți?".

🔀 Fără ordine

{1, 2, 3} și {3, 1, 2} sunt ACEEAȘI mulțime. Nu există „primul element" — deci nici indexare cu m[0]!

⚡ Apartenență rapidă

Întrebarea „x e în mulțime?" primește răspuns aproape instant — fără parcurgerea întregii colecții, ca la liste.

Exemplele din programă: drepturile distincte de acces ale unui grup de utilizatori (fiecare drept o singură dată, indiferent câte persoane îl au) · obiectele din două rucsacuri (care sunt comune? care doar într-unul?) · utilizatorii înregistrați pe mai multe platforme, fără dubluri.

Operațiile pe mulțimi — diagrama Venn vie

Cele două rucsacuri din programă: scrie obiectele (numerele) din fiecare, apoi apasă operațiile și privește zonele aprinzându-se.

A = B =

apasă o operație — zona corespunzătoare se aprinde auriu 👆

Traducerea în povești: reuniunea = tot ce e în MĂCAR un rucsac · intersecția = obiectele COMUNE · diferența A−B = ce ai DOAR în primul rucsac. Plus două teste: apartenența (x ∈ A?) și incluziunea (A ⊆ B? — toate elementele lui A sunt și în B).

Clasa set din Python

Teoria mulțimilor, gata implementată. Aceleași operații, sintaxă de o linie.

creare + eliminarea dublurilor

Acolade cu elemente — sau set(listă), care curăță automat dublurile.

›m = {3, 5, 7}

›set([3, 7, 3, 5]) # {3, 5, 7}

add · remove · discard

Adăugare și ștergere; remove pe element inexistent dă EROARE, discard nu.

›m.add(9) # {3, 5, 7, 9}

›m.discard(5) # {3, 7, 9}

operatorii | & -

Reuniune, intersecție, diferență — sau metodele union / intersection / difference.

›A | B # reuniune

›A & B # intersecție

›A - B # diferență

apartenență · incluziune · egalitate

in verifică elementul; <= verifică submulțimea; == egalitatea (ordinea nu contează!).

›3 in A # True

›{1, 2} <= A # incluziune

›{1,2,3} == {3,1,2} # True!

⚗ Laborator set — testează pe mulțimile tale

A = B = x =

alege o operație — sintaxa Python exactă, rezultatul live 👆

Trei capcane de reținut: ① {} creează un DICȚIONAR gol, nu un set — setul gol e set(); ② seturile NU se indexează (m[0] dă eroare) — le parcurgi cu for; ③ remove() pe un element inexistent aruncă eroare — folosește discard() când nu ești sigur.

Exerciții rezolvate — scenariile din programă

Trei probleme în care mulțimea face în 2 rânduri ce lista făcea în 10.

1 · Clienți distincți

O listă de abonamente cu numele clienților (un client poate apărea de mai multe ori). Câți clienți distincți?

1abon = [11, 22, 11, 33, 22, 11]

2clienti = set(abon)

3print(len(clienti)) # 3

2 · Cele două rucsacuri

Obiectele comune și cele aflate doar în primul rucsac — exact enunțul din programă.

1r1 = {1, 2, 3, 4}

2r2 = {3, 4, 5}

3print(r1 & r2) # comune

4print(r1 - r2) # doar în r1

3 · Există dubluri?

O listă are elemente repetate? Compari lungimile — trucul de aur.

1v = [4, 7, 1, 7, 9]

2if len(set(v)) < len(v):

3 print("are dubluri!")

Legătura cu clasa a IX-a: „câți distincți" se rezolva acolo cu vectorul de frecvență sau cu if x not in unice pe liste. Mulțimea face același lucru într-o singură linie — ăsta e câștigul modelului potrivit de date.

5 probleme reale de pe pbInfo — rezolvarea la un click

Aceeași problemă, două stiluri: C++ ca în clasa a IX-a (vectori de frecvență, fără STL) și Python cu set (operatorii | & -). Apasă „vezi rezolvarea" și compară cât cod îți economisește setul.

pbInfo #279

1 · Distincte

Se dă un șir de n numere naturale, ordonate crescător. Afișează elementele distincte, tot crescător.

🔗 enunț pe pbInfo ↗

Șirul e sortat → un element e „nou" doar dacă diferă de precedentul (nu ai nevoie de nicio structură).

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    long long x, prec = -1;
    for (int k = 0; k < n; k++) {
        cin >> x;
        if (x != prec) cout << x << ' ';  // sortat → distinct = diferit de precedent
        prec = x;
    }
    return 0;
}

set() aruncă dublurile, sorted() le ordonează — o linie.

n = int(input())
v = list(map(int, input().split()))
for x in sorted(set(v)):        # set(v) elimină dublurile
    print(x, end=' ')

pbInfo #528

2 · Multimi

Se dau două mulțimi de numere naturale. Afișează reuniunea crescător pe o linie, apoi intersecția crescător pe linia următoare.

🔗 enunț pe pbInfo ↗

Vector de frecvență: marchezi ce apare în A și în B, apoi parcurgi valorile crescător.

#include <iostream>
using namespace std;
int fa[1001], fb[1001];   // pune 1000 = valoarea maximă din enunț
int main() {
    int n, m, x;
    cin >> n; for (int k = 0; k < n; k++) { cin >> x; fa[x] = 1; }
    cin >> m; for (int k = 0; k < m; k++) { cin >> x; fb[x] = 1; }
    for (int v = 0; v <= 1000; v++) if (fa[v] || fb[v]) cout << v << ' ';  // reuniunea
    cout << '\n';
    for (int v = 0; v <= 1000; v++) if (fa[v] && fb[v]) cout << v << ' ';  // intersecția
    return 0;
}

Cu set, reuniunea e | și intersecția e &. Atât.

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
A = set(a)                 # mulțime din prima listă
B = set(b)                 # mulțime din a doua
for x in sorted(A | B):    # reuniunea
    print(x, end=' ')
print()
for x in sorted(A & B):    # intersecția
    print(x, end=' ')

pbInfo #622

3 · Multimi2

Variație pe subpuncte: reuniunea și intersecția a două mulțimi. Aici arătăm și a treia operație — diferența A − B (ce e doar în A).

🔗 enunț pe pbInfo ↗

Aceleași frecvențe — schimbă doar condiția: || reuniune, && intersecție, && ! diferență.

#include <iostream>
using namespace std;
int fa[1001], fb[1001];
int main() {
    int n, m, x;
    cin >> n; while (n--) { cin >> x; fa[x] = 1; }
    cin >> m; while (m--) { cin >> x; fb[x] = 1; }
    for (int v = 0; v <= 1000; v++) if (fa[v] || fb[v])  cout << v << ' ';  // A U B
    cout << '\n';
    for (int v = 0; v <= 1000; v++) if (fa[v] && fb[v])  cout << v << ' ';  // A ∩ B
    cout << '\n';
    for (int v = 0; v <= 1000; v++) if (fa[v] && !fb[v]) cout << v << ' ';  // A − B
    return 0;
}

Trei operatori, trei linii: |, &, -.

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
A = set(a)
B = set(b)
for x in sorted(A | B):    # reuniune
    print(x, end=' ')
print()
for x in sorted(A & B):    # intersecție
    print(x, end=' ')
print()
for x in sorted(A - B):    # diferență (doar în A)
    print(x, end=' ')

pbInfo #293

4 · CifreDistincte

Se dă un șir de numere naturale. Câte dintre ele au toate cifrele distincte? (Un mini-set, dar de cifre 0–9.)

🔗 enunț pe pbInfo ↗

Vector de frecvență pe cifre (0–9): dacă o cifră reapare, numărul NU are cifre distincte.

#include <iostream>
using namespace std;
bool cifreDistincte(long long x) {
    int f[10] = {0};
    if (x == 0) return true;
    while (x > 0) {
        int c = x % 10;
        if (f[c]) return false;   // cifra c a mai apărut
        f[c] = 1;
        x /= 10;
    }
    return true;
}
int main() {
    int n; cin >> n; long long x; int cate = 0;
    for (int k = 0; k < n; k++) { cin >> x; if (cifreDistincte(x)) cate++; }
    cout << cate;
    return 0;
}

Trucul: pe numărul scris ca text, len(set(x)) == len(x) ⇔ toate cifrele sunt distincte.

n = int(input())
v = input().split()             # numerele ca text, ca să vedem cifrele
cate = 0
for x in v:
    if len(set(x)) == len(x):   # set(x) = cifrele unice ale lui x
        cate = cate + 1
print(cate)

pbInfo #453

5 · Distincte1

Se dă n (pe prima linie) și un șir de n numere naturale (pe a doua). Câte valori distincte conține șirul? Citire clasică, cu n dat de la început.

🔗 enunț pe pbInfo ↗

Vector de frecvență: numeri o valoare doar prima dată când o întâlnești.

#include <iostream>
using namespace std;
int f[1001];   // pune 1000 = valoarea maximă din enunț
int main() {
    int n, x, cate = 0;
    cin >> n;
    for (int k = 0; k < n; k++) {
        cin >> x;
        if (f[x] == 0) { cate++; f[x] = 1; }  // prima apariție = valoare nouă
    }
    cout << cate;
    return 0;
}

Setul face totul: len(set(v)) = câte valori distincte. Exact idioma „de aur" din fișă.

n = int(input())
v = list(map(int, input().split()))
print(len(set(v)))    # numărul de valori distincte

Citirea se adaptează la enunț: formatul exact al datelor (câte numere, pe câte linii) îl vezi pe pbInfo — mai sus e miezul rezolvării. Ideea de reținut: în C++ „stil IX" folosești vectori de frecvență, iar în Python setul face aceleași operații într-o linie.

Verificare rapidă

Cinci întrebări — mulțimile pe scurt.

Fișa de sinteză

Modelul neliniar, condensat.

Mulțimea: elemente UNICE, fără ordine, fără indexare — modelul conceptual neliniar din programă.

Operații: reuniune (∪, |), intersecție (∩, &), diferență (−), apartenență (in), incluziune (<=), egalitate.

Creare: {1, 2, 3} sau set(listă) — care șterge dublurile automat. Setul GOL e set(), nu {}!

Metode: add, remove (eroare dacă lipsește!), discard (tăcut), union, intersection, difference.

Trucul de aur: len(set(v)) < len(v) ⇔ lista v are dubluri.

Când mulțime, când listă? Contează ordinea sau pozițiile → listă. Contează doar CE e înăuntru → mulțime.

Exersează: pe pbinfo.ro caută problemele cu „elemente distincte" — rezolvă-le o dată cu vectori de frecvență (stil IX) și o dată cu set (stil X), apoi compară lungimea codului.