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. {1, 2, 3}
2. {1, 2}
3. {1, 3}
4. {2, 3}
5. {1}
6. {2}
7. {3}
8. {} (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. (1, 2, 3)
2. (1, 3, 2)
3. (2, 1, 3)
4. (2, 3, 1)
5. (3, 1, 2)
6. (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. 1 ocupă primul loc, 2 ocupă al doilea loc;
2. 1 ocupă primul loc, 3 ocupă al doilea loc;
3. 2 ocupă primul loc, 1 ocupă al doilea loc;
4. 2 ocupă primul loc, 3 ocupă al doilea loc;
5. 3 ocupă primul loc, 1 ocupă al doilea loc;
6. 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

#	Problemă	Dificultate
653.	Numere prin rearanjare	Medie (4 )
654.	Aranjare numere	Ușoară (2 )
187.	Permutari	Ușoară (2 )
651.	Numarul de anagrame	Medie (4 )
649.	Permutari cu repetitie	Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme cu aranjamente

#	Problemă	Dificultate
663.	Numarare cuvinte 5	Ușoară (2 )
306.	Triplu stecher	Ușoară (2 )
661.	Anagrame 2	Medie (4 )
659.	Steag	Medie (4 )
658.	Loterie	Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme cu combinări

#	Problemă	Dificultate
671.	Transformare sir	Medie (4 )
672.	Echipa de volei	Ușoară (2 )
296.	Reclama	Ușoară (2 )
669.	Curier	Medie (4 )
667.	Stars and bars 2	Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Probleme diverse de combinatorică

#	Problemă	Dificultate
723.	Arhitect	Grea (8 )
754.	Aeres	Grea (8 )
189.	Numar submultimi	Ușoară (2 )
681.	Drepte paralele 2	Ușoară (2 )
679.	Baza de numeratie extraterestra	Ușoară (2 )
Vrei mai multe probleme? Pe această pagină găsești întreaga listă de probleme propuse.

Alte resurse sau bibliografie

• PbInfo - Elemente de combinatorică
• Campion
• InfoGenius