De ce contează?
La un concurs cu 3 finaliști — Ana, Bogdan și Corina — se acordă doar premiul I și premiul II. Câte clasamente diferite pot apărea? „Ana I, Bogdan II” e altceva decât „Bogdan I, Ana II” — aceiași doi oameni premiați, dar cu locurile schimbate. Deci ordinea contează, și alegem doar 2 din cei 3. Asta e un aranjament.
Intuiția
Un aranjament de k elemente dintr-o mulțime de n este o alegere ordonată de k elemente distincte: contează ce alegi, dar și în ce ordine. E ca o permutare care se oprește mai devreme — completezi doar k poziții, nu toate n. Numărul lor este A(n,k) = n! / (n-k)!: pentru fiecare combinare de k din n există exact k! ordonări ale ei, deci aranjamentele sunt permutările combinărilor.
Două idei te scapă de orice memorare. Prima: un aranjament e o permutare
care se oprește la adâncimea k, nu la n — deci ai nevoie de aceeași mașinărie
(backtracking cu folosit[]), doar cu altă condiție de oprire. A doua:
fiindcă ordinea contează, NU impui indici crescători. La combinări impui
crescător exact ca să nu numeri 12 și 21 de două ori; aici vrei amândouă, deci
parcurgi mereu de la 1.