ISSN 0351-6652 Letnik 31 (2003/2004) Številka 1 Strani 22-27
Martin Juvan:
O RAZVRSTITVAH IN PERMUTACIJAH
Ključne besede: kombinatorika, računalništvo, razvrstitve, permuta-cije.
Elektronska verzija: http://www.presek.si/31/1538-Juvan.pdf
© 2003 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
O RAZVRSTITVAH IN PERMUTACIJAH
Pri programiranju se včasih zgodi, da je treba dane objekte razvrstiti na vse možne načine in za vsako razvrstitev preveriti, ali ima neko želeno lastnost. Seveda je tako preverjanje smiselno le za majhne skupine objektov. Če je namreč v skupini n objektov, potem je vseh razvrstitev ravno ■n! = n- (n — 1) ■.. .-2 -1. Na prvo mesto lahko postavimo katerikoli objekt, na drugo kateregakoli od preostalih n — 1 itd. Števila nI pa se zelo hitro večajo: 5! = 120, 10! = 3628800, 20! = 2.43 ■ 1018.
Matematično razvrstitve predstavimo s permutacijami. Naj bo X (končna) množica z n elementi. Da poenostavimo pisavo, običajno vzamemo X ~ {1.2,..., n}. Formulacije množice X so natanko bijektivne preslikave iz množice X nazaj v množico X. Množico vseh pennutacij označimo z Sx, S(Xj ali pa kar z Sn. Naj bo tt permu taci j a množice A', torej bijektivna preslikava tt:A —» X. Ce n ni prevelik, jo pogosto podamo s tabelo
_( 1	2 ... 77. \
* U(l) tt(2) ... K(n)J-
Za razvrstitev, ki jo določa per mutacij a, vzamemo kar spodnjo vrstico gornje tabele. Vrednost jr(l) tako pove, kateri objekt je na mestu 1, vrednost Jr(2), kateri objekt je na mestu 2, itd. Možna je tudi nasprotna interpretacija, pri kateri vrednost n(i) pove, na katerem mestu v razvrstitvi, ki pripada permutaciji jt, se nahaja objekt i,
S permu taci jami lahko tudi računamo. Ce vzamemo dve permutaciji iste množice, lahko naredimo njun kompozitum (kot kompozitum preslikav) in spet dobimo permutacijo iste množice. Tu smo upoštevali, da je kompozitum bij fiktivni h preslikav spet bijektivna preslikava. Spomnimo se, da kompozitum preslikav označujemo s o in da je definiran kot (tti o -2)(a:) := it i (1x2 (x)). Na primer, pri n = 5 vzemimo
f 1 2 3 4	5 ^ .	{l 2 3 4 5 \
4 2 5	l) 111	^ ~ y 2 1 5 3 4 J '
Potem je
Mimogrede opazimo, da t^ot^ / tt-t o tt i. Učeno pravimo, da kompozitum permu taci j ni komutativna operacija. Je pa kompozitum asociativna operacija, kar pomeni, da lahko "prestavljamo oklepaje". Za vsako trojko per mutacij tti, tt2, tt3 € Sn namreč velja (jti 0^)0^3 = tt\ o(jr2ojr;)). Kot vse bijektivne preslikave imajo tudi permutacije m verze. Ce permntacija preslika i v j. potem njen in verz preslikaj v i. In verz permutacije tt bomo označili s tt-1.
Pri računanju je zelo pomemben zapis permutacij v obliki produkta ločenih ciklov. Poglejmo primer. Vzemimo permutacijo tt £ S<j:
_ f \ 2345678 9\ 2 4 1 5 9 3 6 8]'
Opazimo, da tt preslika 1 v 7, 7 v 3, 3 v 4 in 4 nazaj v 1. Podobno gre 6 v 9, 9 v 8 in 8 nazaj v 6. Elementa 2 in 5 ostaneta na svojih mestih. Pravimo L udi, da sta fiksni točki permutacije. Permutacijo n lahko zapišemo tudi kot
k - (1 7 3 4) o (2) o (5) o (6 9 8) - {1 7 3 4)(6 9 8) = (8 6 9)(7 3 4 1).
Tu zapis (ii ¿2 • ■ ■ ¿fc) označuje cikei, permutacijo, ki ¿i preslika v ¿2, ¿2 v i3 itn. do i/c, ki gre nazaj v i\. Zapis permutacije v obliki ločenih ciklov ni enoličen: zapis posameznega cikla lahko začnemo s poljubnim njegovim elementom (npr. (17 3 4) = (7 3 41)), pa tudi cikle lahko navedemo v poljubnem vrstnem redu. Cikli so ločeni, noben element, ne nastopa v več ciklih, ampak vsak v natanko enem. V navadi je, da pri zapisu fiksne točke (cikle dolžine 1) izpuščamo. Seveda pa moramo potem za celotni opis permutacije poznati še število n. Prav tako izpuščamo znak za kompozitum med cikli. Kadar imamo permutacijo zapisano kot produkt ločenih ciklov, lahko njen inverz dobimo tako, da vse cikle obrnemo:
7T_1 = (1 43 7)(6 8 9).
Povejmo še, kako razvrstitev premešamo v skladu s permutacijo r. To storimo tako, da za vsak i od 1 do n objekt, ki je na mestu i, prestavimo na mesto r(i% Poglejmo primer. Vzemimo razvrstitev B, D, A, E, C in jo premešajmo v skladu s 3-ciklom (14 3). Dobimo razvrstitev A, D, E, B, C. Recimo, da začetno razvrstitev določa permu tac ija tt. Katera permu taci j a določa premešano razvrstitev? Krajši razmislek pokaže, da je to permuta-cija. tt o r-1. Res, kar poglejmo, kateri objekt je v premešani permutaciji na mestu i. Tisti, ki je na začetku na mestu, ki ga r preslika v i. To mesto je t-1 (t), tam pa je objekt 7r{r {i}) — (7roT_1){i),
Po nekoliko daljšem uvodu smo tako prišli do jedra prispevka. Predstavil bi vam rad štiri desetletja star postopek, s katerim lahko zgradimo vse razvrstitve (oz. permutacije), vsako natanko enkrat. V postopku bomo razvrstitev predstavili z enorazsežno tabelo p, pri čemer bodo indeksi v mejah od 1 do n. Kadar bomo nanjo pogledali kot na permutacijo, bo to spodnja vrstica iz dvovrstičnega zapisa permutacije v obliki tabele z zfičetka prispevka. Splošna shema, v katero sodi naš postopek, je rekur-zivna:
permutacije(p, n) za i = 1,2,.... n - 1 ponovi
če je n > 2, pokliči permutacijefp, n — 1), sicer preglej p v p zamenjaj elementa na mestih n in f(n,i) do tod
če je n > 2, pokliči permutacijefp. n — 1), sicer preglej p
Pri pravilnem delovanju postopka pričakujemo, da bo na mestih, kjer pregledamo tabelo p. v njej vsakič druga razvrstitev. Razvrstitev, ki se v tabeli nahaja ob začetnem klicu, je lahko poljubna, res pa je, da bo postopek to razvrstitev obravnaval kot. tisto, ki ustreza identični permutaciji.
Bistvo postopka se skriva v izbiri predpisa f, ki določa, kako med seboj zamenjujemo elemente tabele. Predpis mora zagotoviti, da bomo res zgradili vse razvrstitve. Na prvi pogled pa niti ni jasno, ali tak predpis sploh obstaja. No, R. R. Heap je leta 1963 opazil, da za / lahko vzamemo
,, .. f 1, če je n lih, /(h, t) := < .' . . j L 7, ce je n sod.
V nadaljevanju prispevka se bomo poskušali prepričati, da z zgornjo izbiro res dobimo vse razvrstitve. Razmislek bo zahteval kar nekaj računanja s permutacijami
Poglejmo najprej majhne primere. Ce je n = 1, se telo zanke sploh ne izvrši, edino razvrstitev pa pregledamo v zadtiji vrstici. Pri n — 1 se telo zanke izvede enkrat. V njem pregledamo začetno razvrstitev, nato pa zamenjamo elementa na mestih 1 in 2 (/(2,1) = 1 in n = 2), Po koncu zanke pregledamo še drugo razvrstitev.
V splošnem pa razmišljajmo takole. Če je n. > 2, klic podprograma permutacije izvede n rekurzivnih klicev, n — 1 v zanki in ettega po koncu zanke. Prepričati se moramo, da se pri rekurzivnih klicih na mestu n zvrstijo prav vsi elementi. Nato upoštevamo predpostavko, da rekurzivni
klici (pri njih ima drugi parameter manjšo vrednost) res naredijo vse razvrstitve elementov na. mestih od 1 do n — 1, in tako dobimo vse razvrstitve vseli n elementov. Takemu načinu razmišljanja pravimo dokazovanje z matematično indukcijo. Bazo indukcije, preverjanje trditve za n = 1 in n = 2, smo že premislili v prejšnjem odstavku. Ravnokar pa smo opisali tudi načrt za dokaz indukcijskega koraka.
Če želimo razumeti, kako se izmenjujejo elementi na zadnjem mestu, moramo vedeti, kako rekurzivni klic premeša elemente na prvih n — 1 mestih. Označimo s r„ permu taci jo, v skladu s katero je po klicu permutacije(p, n) premešana tabela p. S sledenjem postopku (ali pa s pomočjo programa, ki izvaja opisani postopek) ugotovimo, da velja rj — - (12), r3 = (13), r4 = (1432), r5 = (15), r6 = (165234), r7 = = (1 7) in rg = (18723456). Z nekaj smelosti postavimo domnevo, da je permutacija Tn enaka 2-ciklu (In), če je n lih, in enaka n-ciklu (1 n n—1 2 3 ... n — 2), če j en sod.
Obnašanje postopka bomo opisali s permutacijami. Naj bo ffj, 1 < i < n, permutacija, ki določa razvrstitev tik pred i-tim rekurzivnim klicem. Iz opisa postopka sledi, da za i = 1, 2,..., n — 1 velja
_ J 7t£ o r^it o (1 n), če je n lih, 1+1 \ ttí o r~Í: o (i n), če je n sod.
Prvi kompozitum ustreza rekurzivnernu kiicu, drugi pa sami zamenjavi v postopku. Pri tem smo upoštevali, da so 2-cikii kar sami svoji in-verzi. Razvrstitev, ki je v tabeli p po koncu klica, pa ustreza permutaciji
Dokazovanje pravilnosti postopka smo tako prevedli na povsem računski. algebraični problem. Pokazati moramo, da so elementi ír¿(n), i = 1,..., ti, med seboj različni (kar pomeni, daje pri vsakem rekurzivnem klicu na mestu n drugačen element) in da je 7rn o , = iri ot„_1 (kar pomeni, da je končna razvrstitev ravno s permutacijo rn premešana začetna razvrstitev tti). Brez škode lahko vzamemo, da je tti identična permutacija. V računu bomo glede na parnost števila n ločili dve možnosti.
Naj bo n liho število. Potem je
x2 — rn*¡ o (1 71) = (1 n —3 tí—4 ... 2 7i~2 n— 1) (1 n) — (ln n —3 n —4 ... 2n-2n-l)
cikel dolžine n. Velja tudi tt, = Tri,-1. Ciklična permutacija vsak element krožno preslika v njegovega naslednika. Podobno velja za potenco cikla, le da moramo narediti toliko korakov naprej po ciklu, kolikor je vrednost eksponenta. Tako ugotovimo, da velja
i	1 2	i	. . 77.-3 71 — 2	71—1 71
fljfn)	ti n — 3	n — i — 1	2 n-2	71-1 1
Ker so v spodnji vrstici tabele sama različna števila, je prvi del trditve dokazan. Poglejmo še izraz jrn o r~_' t. Če upoštevamo, da je k-ta potenca cikla dolžine k identična permutacija, sledi še drugi del trditve:
t« o = ttr1 ° o (ln) o (1 n) = jr2" o (1 n) = (1 Ti) = t"1 .
Ostane še možnost, ko je n sodo število. Tedaj je = (1 n —1). Tako z nekaj računanja dobimo
jt2 = (1 n—1) o (1 n) = (n —1 1 n), TTa = 7t2 o (1 71 — 1) o (2 n) = (n -1 n 2), 7T4 = tt-j O (1 n—1) O (3 ft) = (ti — 1 1 n 3 2), tt5 = 71*4 o (1 n—1) o (4 Ti) = (tj — 1 n 4 3 2), jr6 =7r5 o{1 Ti-l) o (5 n) = (ti-1 1 n 5 4 3 2). Natančneje, za lihe i > 1 velja
tr; — (n-1 ti i — 1 i — 2 ... 3 2),
za sode i / 7i pa
7Ti = (n-1 1 n i-1 i —2 ... 3 2). Zadnja permutacija jrn je enaka
fn=Tn-l°(I TI—1) o (n — 1 7l) = (1 7l) (71—1 n —2 ... 3 2). Tako dobimo
i	1 2 3	4 .	i	. 71 — 1 71
■Ki(n)	71 Ti-1 2	3 .	. i-1 .	. 71-2 1
V spodnji vrstici t-abele so zopet sama različna števila, tako da prvi del trditve drži. Poračnnajmo še tt„ 07^:
*n ornil = (1 n) (n- 1 n-2 ... 3 2) (1 n-l)
= (l ri-2 u—3 ... 3 2 n-l n) = t~1 .
S tem je pravilnost postopka dokazana.
Opisanega postopka vam gotovo ne bo težko pretvoriti v program, ki bo s pomočjo rekmzije zgradil vse razvrstitve. Bolj izkušenim programerjem pa predlagam, da poskusijo napisati nerekurzivno različico postopka. Ta mora seveda graditi razvrstitve v povsem enakem vrstnem redu kot reknrzivna. Po mojih izkušnjah naj bi bila tudi za slabo petino hitrejša (je pa to seveda odvisno od računalnika in prevajalnika, ki ga. uporabljate).
V prispevku smo spoznali Heapov post,opek za. pregled vseli razvrstitev (oz. permutacij), ki ga, je preprosto opisati, precej težje pa se je prepričati, da deluje pravilno. Za dokazovanje pravilnosti smo izbrali bolj algebraično, matematično korektno pot, ki pa ni najbolj nazorna. Smo se pa pri tem vsaj poskušali naučiti osnov računanja n permutacijarni.
Martin Juvan