Permutări

O permutare a unei mulțimi de n elemente e o așezare a elementelor într-o ordine. Două permutări diferă dacă au ordinea diferită.

Câte permutări are o mulțime de n elemente?

Folosim principiul produsului:

• Pe prima poziție: n opțiuni
• Pe a doua poziție: n - 1 opțiuni (am folosit una)
• Pe a treia poziție: n - 2 opțiuni
• …
• Pe ultima poziție: 1 opțiune

Total: n * (n-1) * (n-2) * ... * 1 = n!

P(n) = n!

Valori mici

Factorialele cresc foarte repede.

Exemple

Exemplul 1: așezarea oamenilor

În câte moduri pot așeza 5 persoane pe o bancă?

→ 5! = 120 moduri.

Exemplul 2: anagrame

Câte anagrame ale cuvântului "CARTE" (5 litere distincte) există?

→ 5! = 120.

Exemplul 3: câte ordini de citire a 8 cărți?

→ 8! = 40.320.

Permutări cu repetiție

Dacă mulțimea are elemente repetate, numărul de permutări distincte scade.

Pentru n obiecte, din care k₁ sunt de primul fel, k₂ de al doilea fel, …, kₘ de al m-lea fel (cu k₁ + k₂ + ... + kₘ = n):

P(n; k₁, k₂, …, kₘ) = n! / (k₁! * k₂! * … * kₘ!)

Exemplu: anagrame pentru “BANANA”

6 litere: 3 de A, 2 de N, 1 de B.

Permutări = 6! / (3! * 2! * 1!) = 720 / 12 = 60

Doar 60 anagrame distincte, nu 6! = 720.

Exemplu: “MISSISSIPPI”

11 litere: 1 M, 4 I, 4 S, 2 P.

Permutări = 11! / (1! * 4! * 4! * 2!) = 39.916.800 / 1152 = 34.650

Cod: calcularea n!

Iterativ

long long factorial(int n) {
    long long rez = 1;
    for (int i = 1; i <= n; i++)
        rez *= i;
    return rez;
}

Pentru n = 20, rezultatul încape în long long. Pentru n > 20, folosește aritmetică modulară sau BigInt.

Recursiv

long long factorial(int n) {
    return n <= 1 ? 1 : (long long)n * factorial(n - 1);
}

Generarea permutărilor

Ca să generăm toate permutările unei mulțimi, folosim algoritmul succesor (vezi lecția “Algoritmi de tip succesor”) sau recursivitate/backtracking.

Cu STL (simplu)

#include <algorithm>
#include <iostream>
using namespace std;

int v[] = {1, 2, 3};
int n = 3;

int main() {
    sort(v, v + n);
    do {
        for (int i = 0; i < n; i++) cout << v[i] << " ";
        cout << "\n";
    } while (next_permutation(v, v + n));
    return 0;
}

Ieșire:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

next_permutation generează următoarea permutare în ordine lexicografică.

Probleme clasice

1. Cercuri (așezare circulară)

Câte moduri sunt de a așeza n persoane în jurul unei mese rotunde?

Răspuns: (n-1)!

De ce? O rotație a mesei nu schimbă așezarea (persoana A la nord sau sud e aceeași aranjare). Fixăm o persoană și aranjăm celelalte n-1 → (n-1)!.

2. Permutări cu poziții fixe

Din cele n! permutări, câte fixează elementul 1 pe prima poziție?

Răspuns: (n-1)! (celelalte n-1 elemente pot fi aranjate liber).

3. Derangements (fără puncte fixe)

Câte permutări nu au niciun element pe poziția sa?

Răspuns: D(n) = n! * Σ(-1)^k / k!, aproximativ n! / e. (Vezi lecția PInEx.)

Cod complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

long long factorial(int n) {
    long long rez = 1;
    for (int i = 2; i <= n; i++) rez *= i;
    return rez;
}

int main() {
    int n;
    fin >> n;
    fout << n << "! = " << factorial(n);
    return 0;
}

date.in:

6

date.out:

6! = 720

Greșeli frecvente

1. n! în int

int fact = 1;
for (int i = 1; i <= 15; i++) fact *= i; // OVERFLOW!

13! depășește int (2 miliarde). Folosește long long (până la 20!) sau mod.

2. Permutări vs combinări

Dacă ordinea contează → permutări (sau aranjamente). Dacă nu contează → combinări.

“Câte moduri de așezare în ordine?” → permutări. “Câte grupuri pot forma?” → combinări.

3. Repetiții ignorate

Anagrame pentru “AAA” = 1 (nu 6!). Împarte la k! pentru fiecare literă repetată.

4. 0! = 1

Prin convenție, 0! = 1 (util în formule). Nu e “nedefinit”.

Ce să reții

• Permutare = așezare în ordine.
• P(n) = n! permutări ale unei mulțimi cu n elemente distincte.
• Pentru elemente repetate: n! / (k₁! * k₂! * ... * kₘ!).
• n! crește foarte rapid - folosește long long sau mod pentru n mare.
• Așezare circulară: (n-1)! (fixăm o persoană).
• Pentru generare, folosește next_permutation din STL sau algoritm succesor.