Zabavno dejstvo iz sveta matematike
1/998001 nam da urejeno zaporedje od 000 do 999. 1/998001 = 0.000001002003004...

Zabavno dejstvo iz sveta računalništva
Leta 1936 so Rusi naredili računalnik na vodo. (Vir: http://gizmodo.com/5879106/the-russian-computer-that-ran-on-water)

Permutacije

Moderatorji: hinkopihpih, Matic Conradi

lukazlatecan
Site Admin
Prispevkov: 23
Pridružen: Po Apr 24, 2017 5:29 pm
Kraj: Celje

Permutacije

OdgovorNapisal/-a lukazlatecan » Če Jun 01, 2017 1:58 pm

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)
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. - Leonhard Euler

Vrni se na “Poskusno kolo”

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 3 gosti