De ce contează?
La un concurs cu 5 participanți, în câte feluri se poate forma podiumul (locurile 1, 2, 3)? Aici ordinea contează — cine ia aurul nu e totuna cu cine ia bronzul. Alegi 3 din 5, dar ordonat. Acestea sunt aranjamentele.
Ce este un aranjament
Un aranjament de k elemente din n e o alegere ordonată de k elemente. Spre
deosebire de combinare, ordinea contează: (1,2) și (2,1) sunt aranjamente diferite.
Numărul lor: A(n,k) = n · (n−1) · ... · (n−k+1). Pentru n=3, k=2: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2) — 6 aranjamente.
Legătura cu combinări și permutări
A(n, k) = C(n, k) · k!
Un aranjament = alegi care k elemente (o combinare), apoi le ordonezi (o permutare
a celor k). De aceea aranjamentele sunt mai multe decât combinările.
Cazuri particulare: A(n, n) = n! (toate elementele, ordonate = permutări); A(n, 1) = n (alegi un element). Aranjamentul „interpolează" între aceste extreme.
Generare: permutări oprite la k
Generarea e ca la permutări — cu folosit[] ca elementele să nu se repete — dar te
oprești după k poziții, nu n:
#include <iostream>
using namespace std;
int n, k;
int sol[20];
bool folosit[20];
void genereaza(int pas) {
if (pas == k) { // am ales si ordonat k elemente
for (int i = 0; i < k; i++) cout << sol[i] << " ";
cout << "\n";
return;
}
for (int val = 1; val <= n; val++) {
if (!folosit[val]) {
folosit[val] = true; // alege
sol[pas] = val;
genereaza(pas + 1); // exploreaza
folosit[val] = false; // backtrack
}
}
}
int main() {
n = 3; k = 2;
genereaza(0); // 12 13 21 23 31 32
return 0;
}Singura diferență față de permutările complete e cazul de bază pas == k (nu pas == n).
Restul — folosit[], alege/explorează/backtrack — e identic. Aranjamentele sunt „permutări
parțiale".
Tabloul celor patru generări
| Generare | Ordinea contează? | Toate elementele? | Câte |
|---|---|---|---|
| submulțimi | nu | nu (orice mărime) | 2ⁿ |
| combinări | nu | nu (exact k) | C(n,k) |
| aranjamente | da | nu (exact k) | A(n,k) |
| permutări | da | da (toate n) | n! |
Complexitate
| Operație | Timp | Spațiu |
|---|---|---|
| generarea tuturor aranjamentelor | O(A(n,k) · k) | O(n) |
Capcane reale la aranjamente:
- Confuzi cu combinări: la aranjamente ordinea contează (folosești toate ordinile); la combinări, nu. Caz de bază și structură diferite.
- Caz de bază greșit:
pas == nîn loc depas == k→ generezi permutări complete, nu aranjamente de k. - Uiți backtrack-ul
folosit[val] = false: elemente rămân blocate → aranjamente lipsă. - Generezi pentru k sau n mari: A(n,k) crește repede; verifică limitele.
De reținut
- Aranjament = alegere ordonată de k din n; A(n,k) = C(n,k) · k! (alegi, apoi ordonezi).
- Generezi ca permutările (cu
folosit[]), dar cu cazul de bazăpas == k. - Ordinea contează (vs combinări); A(n,n) = n!, A(n,1) = n.