Brojanje inverzija u permutacijama

Zadan je niz brojeva od 1 do N. Koliko permutacija toga niza postoji? N!. Broj inverzija u nekoj permutaciji definiran je kao broj parova gdje je lijevo pozicionirani broj veći od desnoga. Matamatička definicija: Ako je $$1\leq i < j \leq N$$ tada je inverzija ako a[j] < a[i], gdje je a zadani niz. Broj inverzija je ukupan broj ovakvih parova u nekoj permutaciji. Npr. za N = 3 i permutaciju 231 broj inverzija je 2 (2 i 1, 3 i 1). Koliko je maksimalni broj inverzija za neku permutaciju niza od N članova? $$\binom{N}{2} = \frac{N\cdot\left ( N - 1 \right )}{2}$$ Ako je zadan broj N, i broj k, pri čemu k označuje broj inverzija u nizu duljine N, potrebno je odrediti koliko permutacija toga niza ima točno k inverzija.

Prva ideja je da se prođe kroz sve permutacije i za svaku se izračuna koliko inverzija ima. Ako je to baš k tada pribrojimo broj 1 rješenju. Koja je vremenska složenost ovog rješenja: O( N! ). Ovo je loše, možemo li bolje? Naravno, i tražit ćemo rješenje koje radi u polinomnom vremenu, tj. složenost nam mora biti O( N^c) gdje je c konstanta.

Druga ideja je da nađemo neku pravilnost, tj. neku ovisnost broja permutacija u ovisnosti broja inverzija i duljini niza. Inženjerski pristup nam sugerira da si prvih nekoliko nizova zapišemo:

N = 1, k = 0 => 1, ostali su 0, jer postoji samo jedna permutacija

N = 2, k = 0 => 1, to je permutacija 1,2
N = 2, k = 1 => 1, to je permutacija 2,1

N = 3, k = 0 => 1, permutacija 1,2,3
N = 3, k = 1 => 2  permutacije: 1,3,2 i 2,1,3
N = 3, k = 2 => 2  permutacije: 3, 1, 2 i 2, 3, 1
N = 3, k = 3 => 1, permutacija 3,2,1

U primjeru N=3 vidimo da imamo ukupno 6=3! permutacija i sve smo prebrojali. Već sada može se primjetiti određena simetrja, ali ne možemo tvrditi da za veće N to vrijedi prije nego što dokažemo (ali nećemo sada).

Neka svojstva se lako vide, npr. uvijek će za broj inverzija 0 i broj inverzija N! postojati samo jedna permutacija za svaku a to će uvijek biti početni niz i okrenuti niz.

Ideja je sljedeća: Da li možemo ako znamo za N-1 rješenje (za svaki k) konstruirati rješenje za N (za svaki k).

Pokušajmo to ručno izvesti:

Prvo imamo niz [ 1 ], sad možemo dodati broj 2 na početak ili na kraj niza.

N = 2 dobijemo [1 2] ili [2 1]. Idemo pogledati koliki je broj inverzija za svaku od ovih permutacija. Za [1 2] je 0, za [2 1] je 1. Ok, ništa posebno ali radoznalost nas tjera da napravimo sljedeći korak i ubacimo na svaku od tih permutacija broj 3.

N=3 dobijemo [1 2 3], [1 3 2], [3 1 2] i za [2 1] i 3 dobijemo [ 2 1 3 ], [ 2 3 1] i [ 3 2 1]. Koliko je njihov broj inverzija (po istom redosljedu): 0, 1, 2, 1, 2, 3. Možda se već iz ovoga vidi da postoji lijepa veza između nizova duljine N i N-1.

Sad se već dinamika nameće kao rješenje. Znači za N=1, mogući k-ovi su {0}. To se može granati na dvije grane (dodavanje broja 2), mogući k-ovi su {0, 1}. Zatim dodajemo 3 i granamo dalje. Mogući k-ovi su sada {0, 1, 2, 3}, tj od sad na dalje općenito vrijedi da je k iz intervala $$ Od \,\, 0 \,\, do \,\, \frac{N\cdot\left ( N - 1 \right )}{2}$$ Na ovako nacrtanom stablu (koje trenutno nije nacrtano u ovome postu) vidimo da na svakoj razini ima točno N! čvorova. Neka roditelj ima Q inverzija, djeca će imati od Q do Q+N-1 inverzija. Sad je lako. Možemo napraviti DFS i doći do razine koja nam treba te ukupnom rješenju pridodati to što smo našli. Malo memonizacije i složenost je O(N^3). Moguće je napraviti i dinamiku od dna prema vrhu, gdje se prvo nadzire rješenje u O(N^4) ali uoćavanjem da u jednoj petlji zapravo ne trebamo vrtiti još jednu dobije se O(N^3).

Zadatak: http://www.spoj.pl/problems/PERMUT1/