Generarea aranjamentelor

Un aranjament de $k$ elemente din $n$ valori distincte alege $k$ valori fără repetiție, iar ordinea contează. Din $\{1,2,3\}$, aranjamentele de lungime 2 sunt 12, 13, 21, 23, 31, 32: șase rezultate. Spre deosebire de permutări, nu folosim neapărat toate cele $n$ valori.

Un aranjament de $n$ elemente luate câte $k$ este un șir ordonat de $k$ elemente distincte alese dintre cele $n$ ale mulțimii. Ordinea contează, iar un element nu poate apărea de două ori. Numărul lor este $A_n^k=\frac{n!}{(n-k)!}=n(n-1)\cdots (n-k+1)$; pentru $k=n$ aranjamentele sunt permutările. Backtracking-ul este același ca la permutări, cu două deosebiri: soluția are $k$ niveluri, nu $n$, iar cazul complet apare când se ajunge la nivelul $k$. La revenirea dintr-un apel valoarea aleasă se eliberează, ca să poată fi folosită în alte ramuri. Pentru $k=0$ există un singur aranjament, cel vid.

Exemplul 1 — aranjamentele de 2 elemente din $\{1,2,3\}$. Programul citește $n$ și $k$, cu $0\le k\le n\le 10$.

#include <iostream>
using namespace std;
int n, k, x[11];
bool folosit[11] = {};
void gen(int poz) {
    if (poz == k) {
        for (int i = 0; i < k; ++i) cout << x[i];
        cout << " ";
        return;
    }
    for (int c = 1; c <= n; ++c)
        if (!folosit[c]) {
            folosit[c] = true;
            x[poz] = c;
            gen(poz + 1);
            folosit[c] = false;
        }
}
int main() {
    cin >> n >> k;
    if (0 <= k && k <= n && n <= 10) gen(0);
    return 0;
}

Pentru intrarea 3 2 ieșirea este 12 13 21 23 31 32 , adică $A_3^2=3\cdot 2=6$ aranjamente. În gen(0), alegerea 1 ocupă prima poziție. În gen(1), valoarea 1 este deja folosită, 2 produce 12, iar 3 produce 13. La revenire, 1 este eliberat și poate apărea pe poziția a doua în alte ramuri. Invariantul fiecărui apel este că x[0..poz-1] conține valori distincte, marcate exact în folosit.

Exemplul 2 — numerele de două cifre distincte. Aranjamentele de 2 elemente din $\{1,2,3,4\}$ sunt $A_4^2=4\cdot 3=12$: 12 13 14 21 23 24 31 32 34 41 42 43. Dintre ele, cele pare (cu a doua cifră 2 sau 4) sunt 6: 12, 32, 42, 14, 24, 34. Se poate număra și direct: ultima cifră pară are 2 alegeri, iar prima cifră are 3 alegeri (oricare dintre celelalte), deci $2\cdot 3=6$.

Exemplul 3 — costul generării. Fiecare apel încearcă cel mult $n$ valori, deci timpul este limitat superior de $O(n\cdot A_n^k)$ pentru afișarea tuturor rezultatelor; este cel puțin proporțional cu $k\cdot A_n^k$, pentru că fiecare soluție se afișează. Memoria auxiliară este proporțională cu $n+k$. Pentru $n=10$ și $k=5$ numărul aranjamentelor este $10\cdot 9\cdot 8\cdot 7\cdot 6=30240$.

Exemplul 4 — cu și fără repetiție. Codurile de 2 cifre din $\{1,2,3\}$ în care o cifră se poate repeta sunt $3^2=9$: 11 12 13 21 22 23 31 32 33. Dacă cifrele trebuie să fie distincte, rămân $A_3^2=6$, adică exact cele fără 11, 22 și 33. Aranjamentele de 3 elemente din 3 sunt permutările, $A_3^3=3!=6$, iar aranjamentele de 1 element sunt chiar elementele, $A_n^1=n$. Aceste cazuri particulare servesc la verificarea rezultatului unei formule sau a unui program.

Exemplul 5 — o restricție pe prima poziție. Câte numere de trei cifre distincte se pot forma cu cifrele $0,1,2,3$? Fără restricție ar fi $A_4^3=24$ șiruri, dar 012 nu este număr de trei cifre. Prima cifră are 3 alegeri (nu poate fi 0), a doua are 3 (oricare dintre cele rămase, inclusiv 0), a treia are 2, deci $3\cdot 3\cdot 2=18$. Același rezultat se obține scăzând șirurile care încep cu 0: $24-A_3^2=24-6=18$. În program se adaugă în gen condiția if (poz == 0 && c == 0) continue; înaintea marcării valorii, iar ciclul pornește de la c = 0. Primele numere afișate sunt 102 103 120 123 130 132; dintre cele 18, numai 10 sunt pare.

Verifică cele două cerințe: nu se repetă valori și ordinea contează. Dacă repetiția este permisă, numărul șirurilor de lungime $k$ este $n^k$, altă problemă. Dacă ordinea nu contează, se cer combinări. Între cele trei numere există legătura $A_n^k=C_n^k\cdot k!$: fiecare mulțime de $k$ elemente poate fi ordonată în $k!$ moduri. La o restricție asupra unei poziții, alege mai întâi elementul de pe poziția restrânsă, apoi aranjează restul. În program, fiecare soluție este un șir de $k$ valori distincte; dacă ieșirea conține două valori egale într-un șir, marcajul valorilor folosite lipsește sau este anulat prea devreme. Numărul de linii afișate este $A_n^k$ și nu depinde de ordinea în care sunt încercate valorile; ordinea doar stabilește care linie apare prima, 12 pentru valori încercate crescător.

Exemplu în formatul examenului. Câte numere de două cifre distincte, formate cu cifrele din mulțimea $\{1,2,3,4\}$, sunt pare?

• a) 4
• b) 6
• c) 8
• d) 12

Răspunsul corect este b). O cifră a unităților pară poate fi 2 sau 4, deci 2 alegeri. Cifra zecilor trebuie să fie diferită de cifra unităților și poate fi oricare dintre celelalte 3 cifre, deci 3 alegeri. În total $2\cdot 3=6$ numere: 12, 32, 42, 14, 24, 34. Varianta d) numără toate numerele de două cifre distincte, $A_4^2=12$, fără condiția de paritate.

Greșeli frecvente

• Greșit: aranjamentele de $k$ elemente sunt la fel ca combinările.
  Corect: la aranjamente ordinea contează, la combinări nu.
• Greșit: cazul complet apare la nivelul $n$.
  Corect: apare la nivelul $k$, lungimea cerută.
• Greșit: $A_n^k=n^k$.
  Corect: $n^k$ este numărul șirurilor cu repetiție; fără repetiție este $n!/(n-k)!$.

Înainte și după