Combinatorică în C++: permutări, aranjamente, combinări și altele
Combinatorica este o arie din matematică care studiază modalitățile de numărare sau aranjare ale unor elemente.
Probleme de combinatorică apar deseori în concursuri sau olimpiade de informatică, însă chiar și dacă nu te pregătești la acel nivel, cunoașterea acestor noțiuni o să te ajute mult (plus, se studiază și la matematică!).
Mai jos am atașat câteva noțiuni importante, împreună cu o secvență de cod în C++.
Produs cartezian
Fie n
mulțimi: A1, A2, A3, …, An
. Produsul cartezian, A1 × A2 × A3 × … × An
reprezintă numărul de moduri de alege câte un element din fiecare mulțime,
formând un grup de n
elemente.
Produsul cartezian este egal cu |A1| × |A2| × |A3| × … × |An|
, unde |A|
reprezintă numărul de elemente ale mulțimii A
.
Exemplu
Numărul numerelor de două cifre cu prima cifră impară este |{1, 3, 5, 7, 9}| × |{0, 1, 2, 3, …, 9}| = 5 × 10 = 50
.
Implementare C++
Vom citi de la tastatură lungimile șirurilor, nu și elementele acestora, deoarece nu afectează cu nimic produsul nostru final.
int n, lungMult[101], produsCartezian = 1; //lungMult[i] = lungimea mulțimii i
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> lungMult[i];
produsCartezian *= lungMult[i];
}
cout << produsCartezian;
Submulțimile unei mulțimi
Fie o mulțime A
, cu n
elemente. Atunci putem afirma faptul că A
are 2n
submulțimi.
Demonstrație
Demonstrația 1 (produs cartezian). Pentru fiecare element al mulțimii A
,
pentru a forma o submulțime, putem să alegem să adăugăm sau nu elementul
curent la submulțime. Astfel, există 2
variante pentru primul element, 2
variante pentru al doilea element, …, 2
variante pentru al n
-lea element.
În total, sunt 2 × 2 × … × 2 = 2n
variante.
Demonstrația 2 (combinări). O submulțime reprezintă o modalitate de a
alege k
numere dintre cele n
ale mulțimii A
, unde 0 ≤ k ≤ n
. Pentru k = 0
, există Cn0
variante. Pentru k = 1
, există Cn1
variante. Pentru k = 2
, există Cn2
variante. Asemănător pentru restul k
-urilor până la n
.
În total, sunt Cn0 + Cn1 + Cn2 + Cn3 + … + Cnn = 2n
elemente.
Exemplu
Pentru mulțimea {1, 2, 3}
, avem 8
submulțimi:
-
{1, 2, 3}
-
{1, 2}
-
{1, 3}
-
{2, 3}
-
{1}
-
{2}
-
{3}
-
{}
(Mulțimea vidă)
Implementare C++
Vom folosi o structură repetitivă de tip for pentru a calcula 2n
, însă se
poate folosi ridicarea la putere în timp logaritmic sau chiar manipulare de
biți.
int n, nrSubmultimi = 1;
cin >> n;
for(int i = 1; i <= n; i++) {
nrSubmultimi *= 2;
}
cout << nrSubmultimi;
Permutări
O permutare a unei mulțimi este o aranjare a elementelor sale într-o anumită ordine. Mai tehnic spus, PbInfo vine cu următoarea definiție:
Se numește permutare o corespondență biunivocă (bijecție) între o mulțime finită și ea însăși.
Exemplu
Pentru mulțimea {1, 2, 3}
, avem 6
permutări:
-
(1, 2, 3)
-
(1, 3, 2)
-
(2, 1, 3)
-
(2, 3, 1)
-
(3, 1, 2)
-
(3, 2, 1)
Numărul permutărilor
Pentru o mulțime de n
elemente, avem numărul permutărilor Pn = n!
.
Demonstrație. Să zicem că vrem să generăm o permutare. Primul element
poate să fie oricare dintre cele n
numere — așadar are n
posibilități. Al
doilea element poate să fie oricare număr, mai puțin primul număr (deoarece a
fost ales deja) — așadar rămân n - 1
posibilități. Continuăm, până când
ultimul element rămâne cu 1
singură posibilitate. Folosind regula
produsului, avem în total Pn = n × (n - 1) × (n - 2) × … × 1 = n!
permutări.
int n; //Numărul elementelor mulțimii
cin >> n;
int nrPermutari = 1;
for(int i = 1; i <= n; i++) {
nrPermutari *= i;
}
cout << nrPermutari;
Permutări circulare
Să zicem că vrem să așezăm numerele pe un cerc și vrem să determinăm câte
permutări diferite sunt în acest caz. Diferența dintre permutările normale
sunt că la permutările circulare, o rotație circulară a elementelor spre
oricare direcție nu se consideră ca fiind o permutare diferită (e.g. (1, 2, 3) = (2, 3, 1)
), deoarece, dacă așezăm circular numerele, obținem același
rezultat.
Numărul permutărilor circulare ale unei mulțimi cu n
elemente este (n - 1)!
.
Exemplu. Trei prieteni, 1, 2, 3
, stau la o masă. În câte moduri se pot
așeza? (Răspuns: 2! = 2
). Putem observa cele două moduri în imaginea de mai
jos (roșu și albastru) — pentru fiecare modalitate, există 3
permutări care
defapt dau aceeași permutare circulară:
Implementarea permutărilor circulare este următoarea:
int n; //Numărul elementelor mulțimii
cin >> n;
int nrPermutariCirculare = 1;
for(int i = 1; i <= n - 1; i++) {
nrPermutariCirculare *= i;
}
cout << nrPermutariCirculare;
Permutări cu repetiție
Avem n1
elemente de un tip, n2
elemente de alt tip, …, nk
elemente de
alt tip. În total, sunt n = n1 + n2 + … + nk
elemente. Numărul permutărilor
distincte este: .
Exemplu. Numărul de anagrame ale cuvântului tata
este
:
aatt, atat, atta, taat, tata, ttaa
.
Implementarea în C++ calculează factorialul lui n
, precum și factorialul
celor k
numere și calculează răspunsul astfel.
Aranjamente
Să zicem că n
persoane sunt într-o competiție, iar primii k
vor obține un
premiu (ordinea acestora contează). Câte moduri distincte de alegere a
celor k
persoane există?
Exemplu
Candidează n = 3
persoane pe k = 2
locuri. Astfel, rezultatele posibile
sunt:
-
1
ocupă primul loc,2
ocupă al doilea loc; -
1
ocupă primul loc,3
ocupă al doilea loc; -
2
ocupă primul loc,1
ocupă al doilea loc; -
2
ocupă primul loc,3
ocupă al doilea loc; -
3
ocupă primul loc,1
ocupă al doilea loc; -
3
ocupă primul loc,2
ocupă al doilea loc.
Numărul aranjamentelor de n luate câte k este `Ank = ``.
Implementare C++
int n, k, aranjamente = 1;
cin >> n >> k;
for(int i = n - k + 1; i <= n; i++) { //1 * 2 * 3 * … * n / (1 * 2 * 3 * … * (n - k))
aranjamente *= i;
}
cout << aranjamente;
Combinări
Să zicem că avem n
persoane care candidează pe k
locuri (unde toate
locurile sunt la fel, așadar ordinea alegerii nu contează). În câte moduri
putem alege cele k
persoane?
Exemplu
Pentru n = 4
, k = 2
, putem alege:
- Persoanele
1, 2
(2, 1
este aceeași alegere); - Persoanele
1, 3
- Persoanele
1, 4
- Persoanele
2, 3
- Persoanele
2, 4
- Persoanele
3, 4
Numărul combinărilor de n
luate câte k
este `Cnk = ``.
Această formulă mai poate fi rescrisă astfel: Cnk = 
Implementare
int n, k, factn = 1, factk = 1, factnk = 1; //n, k, n!, k!, (n - k)!
cin >> n >> k;
for(int i = 1; i <= n; i++) {
factn *= i;
}
for(int i = 1; i <= k; i++) {
factk *= i;
}
for(int i = 1; i <= n - k; i++) {
factnk *= i;
}
int combinari = factn / (factk * factnk);
cout << combinari;
Probleme propuse
Probleme cu permutări
Setul de probleme 281 nu a fost găsit.
Probleme cu aranjamente
Setul de probleme 282 nu a fost găsit.
Probleme cu combinări
Setul de probleme 283 nu a fost găsit.
Probleme diverse de combinatorică
Setul de probleme 284 nu a fost găsit.
Alte resurse sau bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Cuprinsul lecției
Produs cartezianExempluImplementare C++Submulțimile unei mulțimiDemonstrațieExempluImplementare C++PermutăriExempluNumărul permutărilorPermutări circularePermutări cu repetițieAranjamenteExempluImplementare C++CombinăriExempluImplementareProbleme propuseProbleme cu permutăriProbleme cu aranjamenteProbleme cu combinăriProbleme diverse de combinatoricăAlte resurse sau bibliografieCreează-ți un cont InfoAs și primești…
- Acces la sute de lecții de calitate, cu animații și exerciții
- Acces la peste 800 de probleme de informatică
- Indicații și rezolvări pentru fiecare problemă
- Totul 100% gratuit!
Comentarii 0