  ̌      ̌   
P 46 (2018/2019) 1 27
Še o generiranju permutacij
A V
Uvod
Permutacija je bijektivna preslikava končne množice
A nase. Predstavimo jo lahko kot razporeditev ele-
mentov množice v neko zaporedje. Brez izgube splo-
šnosti lahko pri tem predpostavimo, da množico
A sestavlja prvih n naravnih števil oziroma
A = {1,2, . . . , n}. Zanimajo nas torej urejene iz-
bire vseh elementov iz A, pri čemer ponavljanje ele-
mentov ni dovoljeno. Permutacijo množice A z n
elementi bomo označili kot zaporedje
a = (a1, a2, . . . , an), kjer ai ∈ {1,2, . . . , n} in ai 6=
aj , če i 6= j, za vse i, j ∈ {1,2, . . . , n}.
Znano je, da je število permutacij v množici z n
elementi enako n! = n · (n− 1) · . . . · 2 · 1, pri čemer
z zapisom n! označimo fakulteto naravnega števila
n. Opazimo lahko, da število permutacij glede na
število elementov v množici zelo hitro narašča. Če
je n = 20, je število permutacij množice {1,2, . . . , n}
enako 20! = 2432902008176640000.
V Preseku [2] so nas že zanimali algoritmi za kon-
struiranje vseh permutacij množice z n elementi.
Spomnimo, da je včasih zaželeno, da algoritem vrne
urejeno zaporedje permutacij. Pri tem običajno mi-
slimo na leksikografsko urejenost. Permutacija
a = (a1, a2, . . . , an) je manjša od permutacije
b = (b1, b2, . . . , bn) glede na leksikografsko ureje-
nost, če in samo če je aj < bj za najmanjši j, v kate-
rem se a in b razlikujeta. Permutacija
a = (4,2,3,1,5) je tako manjša od permutacije b =
(4,2,3,5,1), saj se, gledano od leve proti desni, pr-
vič razlikujeta v četrtem elementu in je a4 < b4. Naj-
manjša permutacija množice z n elementi v leksi-
kografski ureditvi je permutacija (1,2, . . . , n), najve-
čja pa (n,n− 1, . . . ,1). Vse permutacije lahko leksi-
kografsko razporedimo od najmanjše do največje in
oštevilčimo od 0 do n!− 1.
Zaradi hitrega naraščanja števila permutacij gene-
riranja vseh permutacij večje množice v praksi ne
moremo izvesti, saj je permutacij hitro zelo veliko in
njihovo generiranje traja preveč časa. Pri reševanju
nekaterih problemov se zato zadovoljimo s tem, da
konstruiramo samo izbrane permutacije, pogosto pa
nas zanima tudi konstrukcija zaporedja naključno
izbranih permutacij.
Na spletni strani projecteuler.net/ so zbrani
nekateri zanimivi matematično računalniški proble-
mi v okviru Projekta Euler. Problem 24 je zastavljen
takole: Poišči milijonto leksikografsko permutacijo
množice {0,1,2,3,4,5,6,7,8,9}. Povedano drugače,
poišči permutacijo množice {0,1,2,3,4, 5,6,7,8,9}
z zaporednim številom 999999 glede na leksikograf-
sko ureditev.
V tem prispevku bomo opisali način, kako kon-
struiramo permutacijo z zaporednim številom i gle-
de na leksikografsko ureditev ter algoritem, ki vrne
naključno izbrano permutacijo. Za majhne množice
bi lahko za ta namen uporabili tudi algoritem, ki ge-
nerira leksikografsko zaporedje vseh permutacij ter
potem vrne i-to permutacijo, kjer je i vhodni poda-
tek ali naključno generirana vrednost med 0 in n!−1.
Opisana rešitev pa je prostorsko zelo potratna in za
večje množice neuporabna, saj število permutacij, ki
jih moramo straniti, hitro preseže velikost delovnega
pomnilnika v računalniku.
Konstruiranje i-te permutacije v leksikografski
ureditvi
Kot smo pokazali v uvodnem poglavju, lahko permu-
tacije glede na leksikografsko ureditev razvrstimo
od najmanjše do največje oziroma jih oštevilčimo z
zaporednimi števili od 0 do n! − 1. Konstrukcija i-
te permutacije je osnovana na posebnem številskem
sistemu, kjer posamezne števke zmnožimo s fakul-
tetami števil od 1 do n − 1 in ga zato imenujemo
faktorialni številski sistem. V faktorialnem številskem
sistemu je vsako celo število i iz množice {0,1, . . . ,
n!− 1} na enoličen način predstavljeno kot
i = x1(n− 1)!+ x2(n− 2)!+ . . .+ xn−11!+ xn0!,
kjer za j ∈ {1, . . . , n} velja, da xj ∈ {0,1, . . . , n− j}.
  ̌      ̌   
P 46 (2018/2019) 128
Ker je xn = 0, lahko zadnji člen tudi izpustimo in
dobimo
i = x1(n− 1)!+ x2(n− 2)!+ . . .+ xn−11!.
Kot primer predstavimo število 81 v faktorialnem
številskem sistemu. Pretvorbo lahko opravimo na
podoben način kot pretvorbo iz desetiškega v dvo-
jiški številski sistem. Namesto zaporednih delitev s
številom 2 v tem primeru po vrsti delimo z zapore-
dnimi naravnimi števili 1,2,3, . . ., tako da po delje-
nju celoštevilski količnik postane deljenec na nasle-
dnjem koraku, ostanek pa predstavlja števko fakto-
rialnega številskega sistema xj , za vsak j med n in 1:
81 = 81 · 1+ 0, x5 = 0
81 = 40 · 2+ 1, x4 = 1
40 = 13 · 3+ 1, x3 = 1
13 = 3 · 4+ 1, x2 = 1
3 = 0 · 5+ 3, x1 = 3
Preverimo, da velja
81 = 3 · 4!+ 1 · 3!+ 1 · 2!+ 1 · 1!+ 0 · 0! =
3 · 24+ 1 · 6+ 1 · 2+ 1 · 1.
Algoritem, ki pretvori naravno število v števke fak-
torialnega številskega sistema x1, x2, . . . , xn, prepu-
ščamo za vajo bralcu.
Najmanjši permutaciji (1,2, . . . , n) v leksikograf-
ski ureditvi ustreza število 0, ki je v opisanem šte-
vilskem sistemu predstavljeno s števkami x1 = x2 =
. . . = xn = 0. Značilnost najmanjše permutacije je,
da je na j-tem mestu permutacije vedno število j ozi-
roma aj = j. To tudi pomeni, da desno od števila aj
ni nobenega števila, ki bi bilo manjše od aj . V splo-
šnem za poljubno permutacijo (a1, . . . , an) velja, da
je pripadajoča števka faktorialnega številskega sis-
tema xj enaka številu elementov manjših od aj , ki
so v permutaciji desno od števila aj .
Ker je v permutaciji (4,2,3,1,5) element 4 na pr-
vem mestu, so desno od njega trije manjši elementi
in dobimo x1 = 3. Na podoben način dobimo še
druge vrednosti xj , ki so prikazane v levem delu ta-
bele 1. Na podlagi števk xj lahko izračunamo zapo-
redno število permutacije (4,2,3,1,5):
3 · 4!+ 1 · 3!+ 1 · 2!+ 0 · 1!+ 0 · 0! = 80.
Poskusimo še ugotoviti, katera je permutacija mno-
žice {1,2,3,4,5} z zaporednim številom 81. Kot smo
že izračunali, velja x5 = 0, x4 = x3 = x2 = 1 in
x1 = 3. Ker je x1 = 3, morajo biti desno od a1
tri števila manjša od a1, iz česar sledi, da je a1 če-
trti najmanjši element množice {1,2,3,4,5} oziroma
a1 = 4. Podobno, ker je x2 = 1, je a2 drugi najmanjši
element množice {1,2,3,5}, torej a2 = 2. Zaradi
x3 = x4 = 1 dobimo a3 = 3 in a4 = 5. Ko vstavimo
v permutacijo prve štiri vrednosti, ostane množica z
elementom 1, zato je a5 = 1.
Vrednosti x1, x2, x3, x4, x5 za permutaciji
(4,2,3,1,5) in (4,2,3,5,1) so prikazane v tabeli 1.
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
3 1 1 0 0 3 1 1 1 0
x1 x2 x3 x4 x5 x1 x2 x3 x4 x5
TABELA 1.
Vrednosti xj za permutacijo (4,2,3,1,5) (levo) in (4,2,3,5,1)
(desno)
Na podlagi zapisanega bi lahko zapisali algoritem,
ki najprej pretvori vhodni podatek i v števke faktori-
alnega številskega sistema x1, x2, . . . , xn in nato po-
išče pripadajočo permutacijo. Algoritem lahko poe-
nostavimo, saj se izkaže, da ni potrebno shranjevati
števk faktorialnega številskega sistema. V ta namen
je potrebno pretvorbo v faktorialni številski sistem
spremeniti tako, da izračun poteka v obratni smeri:
od prve števke x1 do zadnje xn.
Postopek spet pojasnimo za primer i = 81. Naj-
prej 81 delimo s 4!. Dobimo količnik 3, ki je enak vre-
dnosti x1. Na naslednjem koraku ostanek pri prej-
šnjem deljenju delimo s 3!, da dobimo x2. Nato po-
stopek nadaljujemo še za x3 in x4. Kot vemo, vedno
velja x5 = 0, zato lahko zadnji izračun izpustimo:
81 = 3 · 4!+ 9, x1 = 3
9 = 1 · 3!+ 3, x2 = 1
3 = 1 · 2!+ 1, x3 = 1
1 = 1 · 1!+ 0, x4 = 1
Algoritem Vrni permutacijo (Algoritem 1) vrne i-to
najmanjšo permutacijo množice {1,2, . . . , n} glede
na leksikografsko ureditev. V zanki algoritem za vre-
dnost spremenljivke j med 1 in n − 1 izračuna ele-
ment permutacije aj . Pri tem si pomaga z množico
  ̌      ̌   
P 46 (2018/2019) 1 29
E, v kateri imamo elemente množice {1,2, . . . , n}, ki
še niso bili uporabljeni za konstrukcijo permutacije.
Na začetku seveda velja E = {1,2, . . . , n}. Algoritem
spremenljivki x v j-ti ponovitvi zanke priredi vre-
dnost xj . Kot smo že pojasnili, je aj enak (xj + 1).
neporabljenemu elementu množice {1,2, . . . , n}, kar
ustreza (xj+1). elementu množice E, saj po vstavitvi
v permutacijo element aj odstranimo iz E.
Algoritem 1: Vrni permutacijo
1 Vhod: Naravno število n in nenegativno celo
število i
2 Izhod: (a1, a2, . . . , an), i-ta permutacija
množice {1,2, . . . , n} glede na leksikografsko
ureditev
3 E := {1,2, . . . , n};
4 for j := 1 to n− 1 do
5 x := ⌊ i(n−j)!⌋;
6 i := i mod (n− j)!;
7 aj := (x + 1). najmanjši element iz E;
8 E := E \ {aj};
9 an := element iz E;
Če želimo izračunati permutacijo množice, ki ni ena-
ka {1,2, . . . , n}, je potrebno ustrezno spremeniti za-
četno vrednost spremenljivke E. Za rešitev problema
24 bi tako določili E := {0,1,2,3,4,5,6,7,8,9} ter
poklicali algoritem Vrni permutacijo za vhodna po-
datka i = 999999 in n = 10.
Konstruiranje naključno izbrane permutacije
V tem razdelku bomo pojasnili, kako zapišemo algo-
ritem, ki vrne naključno permutacijo množice
{1,2, . . . , n}. Glede na prejšnji razdelek se enostav-
na rešitev ponuja kar sama: na naključen način iz-
beremo število i med 0 in n!− 1 ter nato uporabimo
algoritem Vrni permutacijo (Algoritem 1), ki poišče
i-to permutacijo v leksikografski ureditvi.
Opisana rešitev je sicer res enostavna, a je pri-
merna le za manjše množice. Na začetku prispevka
smo zapisali vrednost 20!, ki je število s kar 20 štev-
kami, kar že presega največje celo število, ki ga ima-
mo običajno na voljo v programskem jeziku. Po-
trebno je torej poiskati algoritem, ki bo deloval tudi
za množice z večjim številom elementov.
Poglejmo najprej, kako bi lahko skonstruirali per-
mutacijo množice {1,2, . . . , n}.
Če začnemo od desne proti levi, velja:
an lahko izberemo na n načinov (izbiramo iz
{1,2, . . . , n});
an−1 lahko izberemo na n − 1 načinov (izbiramo
iz {1,2, . . . , n} \ {an});
an−2 lahko izberemo na n − 2 načinov (izbiramo
iz {1,2, . . . , n} \ {an, an−1});
: ;
a2 lahko izberemo na 2 načina.
Zgornjo konstrukcijo uporabimo v algoritmu na-
ključna permutacija (Algoritem 2). Algoritem vrne
naključno izbrano permutacijo, ki jo zgradi iz naj-
manjše permutacije leksikografske ureditve
a = (1,2, . . . , n), določene v prvi zanki algoritma. V
drugi zanki spremenljivka j teče od n do 2. Na j-tem
koraku zanke algoritem v spremenljivko i shrani na-
ključno število iz množice {1,2, . . . , j} in nato zame-
nja i-ti in j-ti element permutacije a.
Algoritem 2: naključna permutacija
1 Vhod: Naravno število n
2 Izhod: naključno izbrana permutacija
(a1, . . . , an) množice {1,2,. . . , n}
3 for j := 1 to n do
4 aj := j
5 for j := n downto 2 do
6 i := naključno celo število med 1 in j;
7 zamenjaj(ai,aj);
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
2 2 4 2 3 5 1
3 3 4 2 3 5 1
4 1 4 2 3 5 1
5 1 5 2 3 4 1
1 2 3 4 5
j i a1 a2 a3 a4 a5
TABELA 2.
Delovanje algoritma naključna permutacija za n = 5
         
P 46 (2018/2019) 130
V tabeli 2 je prikazano delovanje algoritma na-
ključna permutacija za n = 5, če so spremenljivki
i prirejene zaporedne naključne vrednosti 1, 1, 3
in 2.
Literatura
[1] A. Bacher, O. Bodini, H. Hwang in T. Tsai, Ge-
nerating Random Permutations by Coin Tossing:
Classical Algorithms, New Analysis and Modern
Implementation, ACM Transactions on Algori-
thms, 13, 1–43, 2017.
[2] A. Vesel, Nekaj algoritmov za generiranje per-
mutacij, Presek, 44 (2016/2017) 26–29.
[3] M. A. Weiss, Data Structures and Algorithm Ana-
lysis, Benjamin-Cummings Pub Co, 1991.
×××
̌

̌
 45/6
Pravilna rešitev nagra-
dne križanke iz šeste
številke Preseka je Višin-
ski kot. Izmed pravilnih
rešitev so bili izžrebani
Rok Strah iz Ljubljane,
Marijana Marinšek iz
Celja in Marko Kubale
iz Rogaške Slatine, ki so
razpisane nagrade pre-
jeli po pošti.
×××