Aranjamente — alegi k din n, dar ordinea contează

De ce contează?

La o cursă cu 5 sportivi, premiem primii 3: aur, argint, bronz. Contează cine pe ce loc? Categoric — (Ana-aur, Dan-argint) e altceva decât (Dan-aur, Ana-argint). Când alegi k din n ȘI ordinea contează, ai un aranjament.

Ce este un aranjament

Un aranjament de k din n este o alegere de k elemente în care ordinea contează. Numărul lor: A(n, k) = n · (n-1) · ... · (n-k+1) = n! / (n-k)!.

Observația-cheie

Aranjamentul stă exact între combinare și permutare: alegi k elemente (ca la combinări) și le pui într-o anumită ordine (ca la permutări). De aici A(n,k) = C(n,k) · k!.

Cele trei, una lângă alta

Pentru a alege/ordona din {1, 2, 3}:

A(3,2)

6 aranjamente de 2 din 3. La combinări ar fi doar 3: {1,2},{1,3},{2,3}.

Noțiune	Ordinea contează?	Câte	Formula
Combinări C(n,k)	nu	mai puține	n! / (k!·(n-k)!)
Aranjamente A(n,k)	da	mai multe	n! / (n-k)!
Permutări (k = n)	da	A(n,n) = n!	n!

Implementare C++

Aproape identic cu permutările, dar ne oprim la poziția k:

#include <iostream>
using namespace std;

int n = 3, k = 2;
int sol[20];
bool folosit[20];

void aranjamente(int poz) {
    if (poz == k) {                    // doar k pozitii, nu n
        for (int i = 0; i < k; i++) cout << sol[i];
        cout << " ";
        return;
    }
    for (int val = 1; val <= n; val++) {
        if (!folosit[val]) {
            folosit[val] = true;
            sol[poz] = val;
            aranjamente(poz + 1);
            folosit[val] = false;      // undo
        }
    }
}

int main() {
    aranjamente(0);                    // 12 21 13 31 23 32 (6 aranjamente)
    return 0;
}

Complexitate

Operație	Timp	Spațiu
Generarea tuturor aranjamentelor	O(A(n,k) · k)	O(k)

Greșeli frecvente

Capcane reale:

Cazul de bază poz == n în loc de poz == k. Atunci generezi permutări complete, nu aranjamente de lungime k.
Scoți folosit[] crezând că, fiindcă ordinea contează, nu mai e nevoie — greșit: un element tot nu poate apărea de două ori în același aranjament.
Confunzi A(n,k) cu C(n,k). Aranjamentele sunt de k! ori mai multe decât combinările.
Pui start ca la combinări. Aici NU restricționezi la ordine crescătoare — toate ordinile sunt valide și distincte.

Recapitulare

Un aranjament alege k din n cu ordinea contând; sunt A(n,k) = n!/(n-k)!.
Cod = permutări oprite la poziția k; păstrezi folosit[], nu folosești start.
Relația cheie: A(n,k) = C(n,k) · k! (alegi, apoi ordonezi).