RACU N A L NI STVO
Generiranje vseh
d	-v ■	I	-v ■
množic dane množice -leksikografska ureditev
Andrej Taranenko
-> V prispevku bomo spoznali algoritme, ki se uporabljajo za generiranje vseh možnih podmnožic poljubne dane koncne množice v nekem vrstnem redu.
Naj bo n poljubno naravno število in S = {1, 2,..., n}. Pogledali bomo, kako tvorimo vse podmnožice množice S. Vemo, da je število vseh podmnožic poljubne množice z n elementi enako 2n. S S označimo seznam1 vseh podmnožic množice S. Natanc-neje, S = [So,S1 ,...,S2n_1], pri cemer za vsak i G {0,1,..., 2n _ 1} velja Si ^ s in so vse množice v seznamu S paroma razlicne. Ker konkreten seznam doloca vrstni red elementov v njem, mu recemo tudi ureditev elementov.
Naj bo S = [So,S1,...,S2n_1] ureditev vseh pod-množic množice S. Ker je s tem dolocen vrstni red vseh teh podmnožic, ima vsaka podmnožica Si, za poljubni i G {0,1,...,2n _ 2}, svojega naslednika Si+1 - podmnožico, ki se v izbranem vrstnem redu pojavi neposredno za njo. Množica S2
n_1 pa nima
naslednika oziroma bomo rekli, da je ta nedefiniran. Velja torej:
naslednik(Si) =
0 < i< 2n - 1
fSi+1,
I nedefiniran, i = 2n _ 1.
Naj bo i G {0,1,..., 2n _ 1} in A množica iz seznama S. Število i je rang množice A natanko tedaj, ko je A = Si. Rang množice A v izbrani ureditvi ozna-cimo z rang(A) in recemo, da rangiramo množico A. Funkcija rang : S — {0,1,..., 2n _ 1} je bijektivna.
1V strukturi seznam je pomemben vrstni red elementov. Sezname bomo zapisovali med oglate oklepaje.
Njen inverz oznacimo z derang. Velja torej:
■ rang(A) = i ^ derang(i) = A,
za vse A iz seznama S in vse i G {0,1,..., 2n _ 1}. Ra-cunanje derang(i) imenujemo derangiranje števila i.
Poleg iskanja naslednjega elementa v ureditvi nas bosta zanimala tudi algoritma rangiranja in derangi-ranja. Še vec, naslednika lahko preprosto definiramo s pomocjo rangiranja in derangiranja na naslednji nacin:
naslednik(A) =
derang(rang(A) + 1),
ce rang(A) < |S| _ 1, in
nedefiniran,
ce rang(A) = |S| _ 1.
(1)
Primer 1. Poglejmo dve izmed vseh možnih ureditev podmnožic množice {1, 2, 3}. Prva ureditev naj bo
A =
01234	5	6	7
{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
druga pa
3 =
0 1 2 3 4 5	6	7
{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
Nad posameznimi množicami so zapisani rangi v dani ureditvi. Vidimo lahko, da ima množica {} v obeh ureditvah rang enak 0. Množica {1} ima v ureditvi A rang enak 1, v ureditvi B pa rang enak 4. Za ureditev A je derang(6) množica {2, 3}, za ureditev B pa je derang(6) množica {1, 2}. Naslednik množice {1, 2} v ureditvi A je množica {1, 3}, v ureditvi B pa množica {1, 2, 3}.
28
PRESEK 45 (2017/2018) 3
RACUNALNIŠ TVO
Podmnožico T množice S = {1, 2,...,n} si lahko v računalniku učinkovito predstavimo z binarnim nizom dolžine n, označili ga bomo z B(T). B(T) torej vsebuje n bitov: bn-1bn-2 ■■■bo, pri tem za vsak i G {0,1,...,n - 1} velja:
bi =
| 0, če n - i G T 1, ce n i T.
To pomeni, da je i-ti bit z leve (indeks n - i) enak 1, če je število i v podmnožici, in enak 0, če število i ni v podmnožiči.
Primer 2. Naj bo S = {1, 2, 3} in T = {1, 2}. Ce gledamo na T kot na podmnožičo množiče S, si jo lahko predstavimo s tremi biti (n = 3), in sičer B(T) = 110. Natančneje, b2 = 1, ker velja 3 - 2 = 1 G T, b1 = 1, ker velja 3 - 1 = 2 G T, in b0 = 0, ker velja 3 - 0 = 3 G T.
Vsaki podmnožiči T množiče S = {1,2,...,n} tako priredimo enolično določen niz B(T). Velja tudi obratno, vsak binarni niz dolžine n enolično določa pripadajočo podmnožičo množiče S. Ni težko preveriti, da na ta način dobimo vse možne binarne nize dolžine n. Še več, na nize B(T) lahko gledamo kot na predstavitve čelih števil med 0 in 2n - 1 v dvoji-škem številskem sestavu. Naraščajoča ureditev teh čelih števil, predstavljenih v dvojiškem številskem sestavu, porodi ureditev podmnožič množiče S, ki jo imenujemo leksikografska ureditev. Rang neke množiče T c S je torej enak vrednosti, ki jo predstavlja B(T) = bn-1bn-2...b0 v dvojiškem številskem sestavu:
n- 1
■ rang (T) = £ bi2i.
i=0
Derang števila r, kjer je 0 < r < 2n - 1, pa je pod-množiča U c S, za katero je B(U) enak predstavitvi števila r v dvojiškem številskem sestavu.
i dvojiška • predstavitev r	pripadajoča množiča	
0 000	{}	
1 001	{3}	
2 010	{2}	
3 011	{2, 3}	
4 100	{1}	
5 101	{1, 3}	
6 110	{1, 2}	
7 111	{1, 2, 3}	
TABELA 1.
Leksikografska ureditev podmnožič množiče {1, 2, 3} je torej
■ S =
012345	6	7
{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
Zapišimo še algoritma rangiranja in derangiranja za leksikografsko ureditev podmnožič množiče S = {1,..., n}. Algoritem 1 prikazuje izračun ranga množiče T c s v leksikografski ureditvi. Z zanko for gremo skozi vse elemente množiče S. V pogojnem stavku preverimo, ali element i pripada dani pod-množiči T. S tem v bistvu preverjamo, ali je v B(T) bit bn-i enak 1. Ce je, rangu prištejemo ustrezno po-tenčo števila 2. Računamo torej desetiško vrednost števila B(T), ki jo predstavlja dvojiški zapis.
Algoritem 1: LexRangPodmnoziče(n,T)
1	r = 0
2	for i = n,n - 1,..., 1 do
if i g T then
^ r = r + 2n-i
5 return r
Primer 3. Poglejmo leksikografsko ureditev podmnožič množiče {1, 2, 3}. Torej števila 0 < r < 23 -1 = 7 uredimo v naraščajočem vrstnem redu. Za vsako število pogledamo njegovo predstavitev v dvo-jiškem številskem sestavu, iz česar dobimo pripadajočo podmnožičo.
Algoritem 2 prikazuje, kako v leksikografski ureditvi derangiramo število r, pri čemer je 0 < r < 2n -1. Tudi tokrat zanka for predstavlja sprehod čez vseh n elementov množiče S. V pogojnem stavku preverimo, ali je najbolj desna števka v dvojiškem zapisu števila r enaka 1. Ce je, v množičo dodamo
28	PRESEK 45 (2017/2018) 3

RAČUNALNIŠTVO

element, ki ga ta števka (bit) predstavlja. Deljenje števila r z dva in rezanjem na celi del v dvojiški predstavitvi odreže najbolj desno števko, kar omo-goca, da v vsaki iteraciji zanke preverjamo vrednost najbolj desne števke.
Algoritem 2: LexDerangPodmnoziče(n,r)
1	T = 0
2	for i = n,n - 1,..., 1 do if r mod 2 = 1 then
L T = T u {i}
r = UJ
6 return T
Algoritma za izračun naslednika ne bomo posebej zapisovali, saj lahko neposredno uporabimo zvezo med naslednikom ter rangiranjem in derangiranjem, predstavljeno s formulo (1).
Primer 4. Ta primer naredite sami. Naj bo n = 8 in T = {1, 3,4,6}. S pomočjo algoritma 1 izračunajte rang(T). Katero množico dobite, če s pomočjo algoritma 2 izračunte derang(181)?
V tem prispevku smo za našo osnovno množičo vzeli množičo S = {1,...,n}. Kaj pa, če želimo le-ksikografsko ureditev poljubne množiče A z n elementi? V tem primeru zadostuje, da poiščemo bijek-čijo f : A — S. Tako lahko poljubno podmnožičo X c A rangiramo kot
■	rang (X) = rang(f(X)).
Podobno derangiramo število r, 0 < r < 2n - 1, po naslednji formuli:
■	derang(r) = f-1 (derang(r)).
Pri tem je f-1 inverzna funkčija funkčije f, torej f(X) = Y natanko tedaj, ko je f-1 (Y) = X, kjer je X c A in Y c S.
Na začetku smo videli, da obstaja več različnih ureditev podmnožič dane množiče, leksikografska je le ena od njih. Na primeru 4 lahko opazimo tudi naslednje. Množiča {2, 3} ima rang enak 3, množiča {1} pa rang enak 4. V leksikografski ureditvi pod-množič množiče {1,2, 3} imamo torej dve zaporedni množiči, ki sta komplementarni (sta med seboj različni, kolikor se le da). Ali obstaja taka ureditev
podmnožic množice {1, 2, 3}, da se bosta dve poljubni zaporedni množici razlikovali za natanko en element? Odgovor je DA! Taka razvrstitev obstaja za poljubno množico {1, 2,...n}, kjer je n G N. Ampak to je morda zgodba za kdaj drugič. Vas pa izzivam, da najdete tako razvrstitev podmnožic množice {1, 2, 3}.
Literatura
[1] Donald L. Kreher, Douglas R. Stinson, Combinatorial algorithms: generation, enumeration, and search, CRC Press, 1999.
_ XXX
Nalogi
Marko Razpet
1.	Urejena m-teriča (x1,x2,..., xm-1,xm), v kateri so koordinate x1,x2,..., xm-1,xm naravna števila, je pitagorejska m-teriča, če velja
■x2+xi+...+xm-1 = xm
Pri tem je m > 3. Pitagorejska trojiča je na primer (3, 4, 5), ker je 32 + 42 = 52, pitagorejska četveriča pa (2, 3, 6, 7), saj je 22 + 32 + 62 = 72. Dokaži, da je za vsako naravno število n peteriča
■	(2n, 2n + 1, 2n + 2,6n2 + 6n + 2,6n2 + 6n + 3)
pitagorejska. Poišči tovrstne pitagorejske peteriče, katerih koordinate ne presegajo 100.
2.	Izračunaj
■	62 - 52, 562 - 452, 5562 - 4452, 55562 - 44452 Nato rezultate posploši na razliko kvadratov oblike
^55 . 5; 62 - 44... 4 52.
n	n
XXX
28
PRESEK 45 (2017/2018) 3