Număr de ordine — rangul unei permutări

De ce contează?

Cauți cuvântul „pisică” într-un dicționar. Nu citești toate cuvintele de la început ca să afli a câta intrare este — îți dai seama direct, după prima literă, după a doua, câte cuvinte stau înaintea lui. Permutările se ordonează exact la fel, lexicografic. Astăzi înveți să afli „a câta” este o permutare fără să le parcurgi pe toate.

Ideea: ordine lexicografică și câte permutări o iau înainte

Permutările mulțimii {0, 1, ..., n-1} se pot așeza în ordine lexicografică, adică „de dicționar”: compari primul element, apoi al doilea, și așa mai departe. Pentru n = 3 ordinea completă este:

rang 0: (0, 1, 2)
rang 1: (0, 2, 1)
rang 2: (1, 0, 2)
rang 3: (1, 2, 0)
rang 4: (2, 0, 1)
rang 5: (2, 1, 0)

Rangul unei permutări este câte permutări sunt strict mai mici decât ea. Prima are rangul 0 — nimic nu o ia înainte.

Cum îl calculezi fără să le listezi? Mergi poziție cu poziție. Pe fiecare poziție te întrebi: câte permutări încep la fel ca a mea până aici, dar pun pe poziția curentă un element mai mic decât al meu? Dacă pe poziția curentă elementul tău sare peste k elemente mai mici și nefolosite, atunci sari peste toate aranjamentele celor (rămase) poziții care ar fi stat sub fiecare astfel de alegere — adică k * (rămase)! permutări. Aduni aceste contribuții.

Exemplu pas cu pas

Să calculăm rangul permutării (2, 0, 1) din mulțimea {0, 1, 2}. Avem n = 3. Ținem evidența elementelor încă nefolosite.

Poziția 0 (mai rămân 2 poziții, deci factor 2! = 2). Elementul este 2. Nefolosite: {0, 1, 2}. Câte sunt strict mai mici decât 2 și nefolosite? 0 și 1, deci k = 2. Contribuție: 2 * 2! = 2 * 2 = 4. Marchez 2 ca folosit.

Poziția 1 (mai rămâne 1 poziție, factor 1! = 1). Elementul este 0. Nefolosite: {0, 1}. Mai mici decât 0 și nefolosite? Niciunul, k = 0. Contribuție: 0 * 1! = 0. Marchez 0 ca folosit.

Poziția 2 (mai rămân 0 poziții, factor 0! = 1). Elementul este 1. Nefolosite: {1}. Mai mici decât 1? k = 0. Contribuție: 0 * 0! = 0.

Rang total = 4 + 0 + 0 = 4. Verifică în tabelul de mai sus: (2, 0, 1) are într-adevăr rangul 4. Sistemul acesta de scriere (cifre înmulțite cu factoriali) se numește sistemul factorial sau factorial number system.

Implementare C++

#include <iostream>
using namespace std;

// Calculeaza rangul (0-based) al permutarii p[0..n-1]
// in ordine lexicografica. Foloseste long long: n! creste rapid.
long long rangPermutare(int p[], int n) {
    long long rang = 0;
    long long fact = 1;            // va deveni (n-1)! treptat

    // pre-calculam (n-1)! pentru prima pozitie
    for (int i = 2; i <= n - 1; i++) {
        fact *= i;
    }

    for (int i = 0; i < n; i++) {
        // numaram cate elemente mai mici si NEFOLOSITE sunt la dreapta
        int maiMici = 0;
        for (int j = i + 1; j < n; j++) {
            if (p[j] < p[i]) {
                maiMici++;
            }
        }
        rang += (long long)maiMici * fact;   // contributia pozitiei i

        // pregatim factorialul pentru pozitia urmatoare: (ramase-1)!
        int ramase = n - 1 - i;              // pozitii dupa cea urmatoare
        if (ramase > 0) {
            fact /= ramase;                  // (k)! / k = (k-1)!
        }
    }
    return rang;
}

int main() {
    int p[] = {2, 0, 1};
    int n = 3;
    cout << rangPermutare(p, n) << "\n";   // valori: (2,0,1) -> rezultat 4
    return 0;
}

Numărarea elementelor „mai mici la dreapta” funcționează corect chiar și fără un vector separat de „folosite”: orice element din stânga e deja consumat, iar la dreapta verificăm doar ce a rămas. Pentru permutări mari poți accelera această numărătoare cu un arbore indexat binar (Fenwick), ducând complexitatea la O(n log n).

Complexitate

Pas	Timp	De ce
Numărare elemente mai mici la dreapta	O(n) per poziție	parcurgi sufixul
Total peste toate pozițiile	O(n²)	n poziții × O(n)
Spațiu suplimentar	O(1)	doar `rang` și `fact`

Observația-cheie

Contribuția fiecărei poziții este „cifra” ei în sistemul factorial: pe poziția i cifra poate lua valori de la 0 la n-1-i și are „greutatea” (n-1-i)!. De aceea suma maximă este (n-1) * (n-1)! + ... + 1 * 1! + 0 * 0! = n! - 1, exact rangul ultimei permutări.

Greșeli frecvente

0-based vs 1-based: în convenția uzuală prima permutare are rangul 0. Dacă vrei „a câta este” numărat de la 1, adaugi 1 la final. Nu amesteca cele două.
Overflow la factorial: 13! depășește deja int. Ține factorialul și rangul în long long, iar la înmulțire pune cast explicit: (long long)maiMici * fact.
Numeri elementele greșit: trebuie elemente mai mici ȘI nefolosite, aflate la dreapta. Dacă numeri și la stânga sau incluzi elemente deja fixate, rangul iese complet eronat.
Uiți că prima permutare are rang 0: dacă pornești suma de la 1 „ca să fie prima a 1-a”, toate rangurile vor fi deplasate cu o unitate față de teorie.

p	2	0	1
	0	1	2
	×2!	×1!	×0!

Contribuții: 2×2! = 4, apoi 0 și 0. Rang = 4. Fiecare poziție e o cifră a sistemului factorial.

Aplicația inversă: a k-a permutare fără a le genera

Procedeul se poate inversa: dat rangul k, afli direct permutarea, fără a genera toate cele n! aranjamente. Împarți succesiv k la (n-1)!, (n-2)!, ... ; fiecare cât îți spune al câtelea element nefolosit alegi pe poziția curentă, iar restul continuă pentru pozițiile următoare. Pentru rangul 4 cu n = 3: 4 / 2! = 2 rest 0 → iei al treilea nefolosit (2); 0 / 1! = 0 → primul nefolosit rămas (0); ultimul rămâne 1. Obții (2, 0, 1). Asta îți dă „a k-a permutare” în O(n²), fără să le parcurgi pe toate.

Recapitulare

Rangul unei permutări = câte permutări sunt strict mai mici lexicografic; prima are rangul 0.
Pe fiecare poziție numeri elementele mai mici și nefolosite de la dreapta și înmulțești cu factorialul pozițiilor rămase; folosește long long.
Inversând împărțirile la factoriali obții direct „a k-a permutare” în O(n²), fără a le genera pe toate.