i
i
“1393-Juvan-1” — 2010/8/17 — 13:58 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 27 (1999/2000)
Številka 2
Stran 89
Martin Juvan:
KOLIKO MANJŠIH?
Ključne besede: naloge, računalništvo, programiranje, permutacija,
leksikografska ureditev.
Elektronska verzija:
http://www.presek.si/27/1393-Juvan-koliko.pdf
c© 1999 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
MatematiZSno je permutacija mnoiice IN, = El, 2, . . . , a) biiektivna pre- 
slikam iz IN, v INn. Eden od naEinov za opis permutacije Je, da podamo 
predph, ki doloEa, karn se prealikajo pcmamzni elernenti iz N,. Na 
primer: 
Ker je permutdja p m h m  med konbaima mnoiicama, jo lahko opigemo 
tudi s tabdo. Na primer: 
Kadar vemo, da bomo obravnad le permutaicije mnoBce INn, pri zapisu 
s tabelo obiEajno izpuatimo zgomjo mtico, saj let& vsebuje informacijo, 
ki jo fe poanamo. Zapis samo crpodqje vmtim table je tudi obi.Eajm ndin 
predsbvitve pemrrtacije v r&&U pmgmnih. 
Sedajppakdogi. M c & I N ,  dop-n! =I-2. ...-{ n - 1 ) . n  
pwmutacij. Te pesmutaije la& d i m 0  na dike n f i o v .  Zela pagoat0 
sreEamo l a m  d t e v .  To je nreditev, ki jo up0rabljaDI~ tudi 
pri m a u  geml v ldcsik~nih (od tod hdi njeno ime). Naj bosh 
TI in 7r2 rmlieni pemutacaciji in i E lN, wjmwjik Btevilo, za lsstero je 
r ~ ( i )  # .ni(i). Putem je  perrnutix5ja nl pri l e d  ureditvi pred 
permut8ejjo 7r2 uatanko tedaj, ko je q( i f  < ~ ( i ) .  Vda naloga je, da 
napi&te r a E u n W  program, ki bo za dano permutmijo mn&itx N, 
ugotovil, katera po vrsti je pri lekshgrafski ureditvi vseh n! permutacij. 
Na primer, p m t a c i j a  3 4 1 6 2 mnogce INs je pri lekdkograkki ureditvi 
aa 62. m&u. 
Mertin Juvasz