Stran 1 od 1

Permutacije

Objavljeno: Če Jun 01, 2017 1:58 pm
Napisal/-a lukazlatecan
Naj oznaka [n] predstavlja množico {1,2,…,n}. Permutacija reda n je bijektivna preslikava iz množice [n] v množico [n]. Naj bo [math] neka konkretna permutacija reda 7. Po navadi jo predstavimo s takšno tabelico:

[math]

To pomeni, da je [math], itn. Ker je zgornja vrstica vedno 1 2 3…n, jo navadno izpustimo in permutacijo pišemo z besedo, takole:

[math]
Zelo popularen je tudi ciklični zapis permutacije. Začnemo z elementom 1 in pogledamo, kam se ta slika: [math]. Nato pogledamo, kam se slika element 3: [math]. Če s tem nadaljujemo, se bo slej ko prej zgodilo, da bomo prišli nazaj do elementa 1. Res, [math]. Permutacija [math] vsebuje cikel (1 3 4). Vzemimo najmanjše število, ki še ne nastopa v nobenem ciklu – v našem primeru je to 2 – in postopek ponovimo. Sčasoma pridemo do sledečega zapisa:

[math]
Permutacijo reda n pa lahko predstavimo tudi s tabelo inverzij [math], kjer je [math] število tistih elementov, ki so večji od i in se v zapisu permutacije z besedo pojavijo levo od i. V našem konkretnem primeru je tabela inverzij:

3 5 0 1 2 1 0.

Znano je, da lahko vsako permutacijo na en sam način zapišemo s tabelo inverzij in da vsaka tabela inverzij [math], za katero velja[math] za vse i∈[n], predstavlja neko permutacijo.

Napiši program, ki bo tabelo inverzij pretvoril v ciklični zapis permutacije.

Vhodni podatki
Testni primer sestavljata dve vrstici. V prvi vrstici je celo število n, tj. red permutacije. V drugi vrstici je n celih števil, ki so ločena s presledki in predstavljajo veljavno tabelo inverzij.

Omejitve vhodnih podatkov
[math]

Izhodni podatki
Izpiši eno vrstico, v kateri bo ciklični zapis permutacije, ki pripada podani tabeli inverzij. Vsak cikel naj bo v okroglih oklepajih, med cikli pa izpiši po en presledek. Števila znotraj cikla naj bodo ločena med seboj s po enim presledkom. V ciklu naj bo na prvem mestu vedno najmanjši element. Cikli naj bodo urejeni glede na element na prvem mestu. (Glej primere.)

Primeri
Primer vhoda

Koda: Izberi vse

7
3 5 0 1 2 1 0

Pripadajoč izhod

Koda: Izberi vse

(1 3 4) (2 7) (5 6)


Primer vhoda

Koda: Izberi vse

6
4 2 1 1 0 0

Pripadajoč izhod

Koda: Izberi vse

(1 5) (2 3) (4) (6)