Kombinatoriniø objektø generavimo algoritmai

Kombinatoriniø objektø generavimo algoritmai

Šiame paragrafe aptarsime pagrindinius kombinatoriniø objektø (deriniø, këliniø, aibës išskaidymo ir kt.) generavimo algoritmus.

Optimali tokiø objektø generavimo algoritmo struktûra yra:

begin

generuoti pradiná junginá (kombinatoriná objekt¹);

while “generavimo s¹lyga” do

begin

nagrinëti (spausdinti) junginá (kombinatoriná objekt¹);

generuoti junginá (kombinatoriná objekt¹), gretim¹ išnagrinëtam (atspausdintam).

end

end

Priklausomai nuo pasirinktø objektø bei jø generavimo tvarkos, šiame algoritme turi bûti konkretizuoti sakiniai “generuoti pradiná junginá”, “generavimo s¹lyga”, “generuoti gretim¹ junginá”.

Deriniø generavimo algoritmai

Deriniø generavimas leksikografine tvarka

Pirmiausia aptersime deriniø generavimo leksikografine didëjimo tvarka algoritm¹. Apie leksikografinê vektoriø tvark¹ kalbëjome 1.3 paragrafe. Èia priminsime, kad jei á deriná žiûrësime kaip á skaièiø, tai deriniams atitinkantys skaièiai bus išdëstyti didëjimo tvarka.

Pavyzdys. Panagrinëkime . Deriniai, surašyti leksikografine tvarka, bus:

Derinius nuosekliai talpinsime masyve ir šio masyvo elementai apibrëš deriná.

Pradinio derinio generavimas. Aišku, kad pradinis derinys generuojamas taip:

for l 0 to k do c [l] := l;

Kaip generuoti patá mažiausi¹ leksikografiškai didesná deriná nei turimas?

Tarkime, – turimas derinys. Leksikografine tvarka pats didžiausias derinys yra: . Vadinasi, , . todël, norint apskaièiuoti patá mažiausi¹ leksikografiškai didesná deriná nei nagrinëjamas derinys, elgsimës taip:

masyve rasime pirm¹ iš dešinës element¹ c_l, , tenkinantá s¹lyg¹ ;

šá element¹ padidinsime vienetu, t.y. ;

likusius elementus užpildysime iš eilës einanèiais natûraliaisiais skaièiais, t.y.

for i l + 1 to k do c_i: = c_i-1 + 1;

Generavimo pabaigos s¹lyga. Jei pirmasis iš dešinës elementas, tenkinantis s¹lyg¹ , yra , tai reiškia, kad nagrinëjame deriná: . Vadinasi, jau visi deriniai sugeneruoti.

Tuo bûdu, deriniø generavimo leksikografine tvarka algoritmas yra.

Deriniø skaièiaus apskaièiavimo algoritmas

Duota:  n – objektø skaièius,

k – objektø skaièius derinyje.

Rasti:  generuoti derinius leksikografine tvarka.

begin

for l := 0 to k do c [l] := l;

p := true;

while p do

begin

spausdinti deriná

l := k;

while (l >= 1) and c [l] >= n – k + l do l := l – 1;

if l = 0 then p := false

else begin

c [l] := c [l] + 1;

for i := l + 1 to k do c [i] := c [i – 1] + 1;

end

end

end

Treèiasis Grëjaus kodø generavimo algoritmas

Kaip matyti iš antrojo Grëjaus kodo generavimo algoritmo (žr. 1.3 paragraf¹), Grëjaus kodus galima generuoti iš pradinio kodo, žinant sek¹ . Šios sekos elementas žymi skiltá, kuri¹ reikia invertuoti, kad iš -ojo kodo gautume i-¹já kod¹.

Pavyzdžiui, kai , seka T₃ yra tokia: .

Vadinasi, pakanka mokëti efektyviai generuoti sek¹ T_n, kad galëtume generuoti Grëjaus kodus.

Sek¹ T_n galima efektyviai generuoti naudojant stek¹.

Pradžioje stekas užpildomas elementais: (viršuje yra elementas 1). Algoritmas ima viršutiná steko element¹ i ir patalpina já á sek¹ T_n; po to á stek¹ árašomi elementai . Bûtent tokiu bûdu žemiau pateiktas algoritmas generuoja Grëjaus kodus.

begin

s

for j := n downto 1 do begin

g [j] := 0;

s j

end

while s ¹ Æ do

begin

spausdinti

i s

g [i] := 1 – g [i];

for j := i – 1 downto 1 do s j

end

end

end

Skaièiuojant pagal šá algoritm¹, steko turinys (viršutinis elementas yra steko viršûnëje) kis taip: , o i reikšmës sudarys T₃ sek¹ .

Pateikt¹ algoritm¹ galima patobulinti. Kiekvien¹ kart¹, kai á stek¹ patalpinamas elementas , mes apriori žinome, kad virš jo bus patalpinti elementai . Protingas šios informacijos panaudojimas ágalina vietoj steko naudoti masyv¹ tokiu bûdu. Elementas yra viršutinis steko elementas ir kiekvienam yra elementas, steke esantis tuoj po elemento j (žemiau elemento j), jei j yra steke. Jei elemento j steke nëra, tai elemento reikšmë negali turëti jokios átakos skaièiavimams ir todël priskiriame reikšmê , kadangi mes žinome, kad kai kit¹ kart¹ elementas bus patalpintas á stek¹, elementu, esanèiu virš jo, bus elementas j. Dar daugiau, kadangi elementai bus talpinami á stek¹ pašalinus element¹ i, mums reikia tiktai priskirti , laikant, kad visiems j, , reikšmë buvo priskirta, kai j buvo pašalintas iš steko (primename, tada ). Pagaliau, kai , elementai á stek¹ patalpinami operacijos dëka.

Dabar gausime toká algoritm¹.

begin

for j := 0 to n + 1 do begin

g [j] := 0;

t [j] := j + 1;

end

i

while i < n + 1 do

begin

spausdinti

i t

g [i] := 1 – g [i];

t [i – 1] := t [i];

t [i] := i + 1;

if i ¹ 1 then t

end

end

Kai , masyvo t turinys skaièiavimo eigoje kis taip:

Pateikt¹já algoritm¹ galima truputá patobulinti. Pastebësim, jei operatoriø patalpintume po operatoriaus g [i] := 1 – g [i], tai operatoriø if i ¹ 1 then t[0]:=1 galima išmesti. Iš tikro, jei , tai operatorius
t [i – 1] := t [i] tuoj pat ištaisys neteising¹ t [0] reikšmê. Tuo bûdu galutinis Grëjaus kodø generavimo algoritmas bus toks.

begin

for j := 0 to n + 1 do begin

g [j] := 0;

t [j] := j + 1;

end

i

while i < n + 1 do

begin

spausdinti

i t

g [i] := 1 – g [i];

t t [i – 1] := t [i]; t [i] := i + 1;

end

end

Deriniø generavimas minimalaus pokyèio tvarka

Aptarkome deriniø generavimo minimlaus pokyèio tvarka algoritm¹. Minimlaus pokyèio tvarka – tai tokia deriniø seka, kai bet koks šios sekos derinys yra gaunamas iš prieš já stovinèio derinio, pakeitus jame vien¹ element¹ kitu.

Pavyzdys. Panagrinëkime . Deriniai, surašyti minimalaus pokyèio tvarka, bus tokie:

Nesunku pastebëti, kad bet koks šios sekos derinys, išskyrus pirm¹já, yra gaunamas iš prieš já stovinèio derinio, pakeitus vien¹ element¹ kitu.

Jei pirmajame derinyje element¹ 2 pakeisime elementu 4, tai gausime antr¹já deriná. Jei jame element¹ 1 pakeisime elementu 2, tai gausime treèi¹já deriná ir t.t.

Reikia pastebëti, kad ši deriniø seka yra užciklinta, t.y. jei paskutiniame derinyje element¹ 5 pakeisime elementu 3, tai gausime pirm¹já šios sekos deriná.

Kiekvien¹ deriná galima užkoduoti n-skilèiu dvejetainiu skaièiumi : jei , tai elementas i priklauso deriniui; jei , tai elementas i nepriklauso deriniui. Tuo bûdu deriniai bus užkoduoti n-skilèiais dvejetainiais skaièiais, kiekvienas iš kuriø turi k vienetukø ir nuliø.

Aišku, kad minimalaus pokyèio deriniø sekos kodai bus dvejetainiai skaièiai, turintys k vienetukø, ir bet kokie du gretimi skaièiai skirsis dviem skiltimis: vienoje nulis keièiamas vienetu, o kitoje vienetas keièiamas nuliu.

Pavyzdys. Aukšèiau pateikto minimalaus pokyèio deriniø sekos kodai bus:

Tokiø kodø generavimas yra glaudžiai susijês su 1.3 paragrafe išnagrinëtu Grëjaus kodø generavimu.

Tarkime, – Grëjaus kodai, o , – seka Grëjaus kodø, turinèiø lygiai k vienetukø. Tada, kaip parodyta literatûroje [RND80], seka sutampa su minimalaus pokyèio deriniø seka.

Pavyzdys. Panagrinëkime Grëjaus kodus, kai . Remiantis 1.3 paragrafe išnagrinëtu algoritmu, gausime toki¹ sek¹:

Kodai, turintys 3 vienetukus, – pabraukti. Išrašê šiuos kodus, gausime minimalaus pokyèio derinio sekos kodus.

Norëdami efektyviai generuoti , , kodus, pasinaudokime rekursyviniu apibrëžimu:

(3.4.1)

ir

èia žymi kodus, surašytus atvirkšèia tvarka, o reiškia, kad n skilèiø užpildome nuliais, o – kad n skilèiø užpildome vienetais.

Pastaroji rekurentinë formulë generuoja pradedant ir baigiant.

Pavyzdys. Remdamiesi (3.4.1) formule, pavaizduokime generavimo medá (žr. 3.4.1 pav.).

1 pav. G(5, 3) generavimas, remiantis (3.4.1) rekurentine formule

Remdamiesi šiuo medžiu, gausime sek¹:

Nesunku parodyti (žr. [RND80]), kad 3.4.1 pav. pavaizduoto binarinio medžio kabanèios viršûnës yra arba arba .

Kodø generavimo uždavinys transformuojasi á binarinio medžio kabanèiø viršûniø peržiûr¹: pradedant viršutine ir baigiant apatine.

Norint pereiti nuo vienos kabanèios viršûnës á gretim¹ kabanèi¹ viršûnê, nagrinëjame keli¹ iš pirmos kabanèios viršûnës medžio šaknies link. Tuo keliu link šaknies keliaujame viršûnëmis, kurios yra apatiniai sûnûs (žr. 3.4.1 pav.). Pasiekê pirm¹j¹ viršûnê, kuri yra viršutinis sûnus, pereiname pas jo brolá (apatiná sûnø) ir iš jo, eidami viršutiniais sûnumis, einame á kabanèi¹ viršûnê.

Pavyzdžiui (žr. 3.4.1 pav.), išnagrinëjê kabanèi¹ viršûnê , pirmiausia pasieksime viršutiná sûnø ir pereisime pas jo brolá (apatiná sûnø) . Ir iš jo viršutiniais sûnumis , pasieksime viršûnei gretim¹ kabanèi¹ viršûnê . (3.4.1 pav. šis kelias paryškintas).

Nagrinëdami kabanèi¹ binarinio medžio viršûnê , mes tuo paèiu žinome keli¹ iš šaknies á kabanèi¹ viršûnê. Norëdami pereiti prie gretimos kabanèios viršûnës, turime saugoti informacij¹ apie viršûnê , á kuri¹ turime sugrážti (viršûnës visada yra apatiniai sûnûs). Šios viršûnës bus saugomos steke. Toliau pateiktame generavimo algoritme stekas bus organizuojamas taip pat, kaip jis buvo organizuotas generuojant Grëjaus kodus (žr. treèi¹já Grëjaus kodø generavimo algoritm¹). Parametras t rodo skaièiø vienetukø tarp skilèiø ir gali bûti nesunkiai apskaièiuojamas. Todël steke saugoma tik i reikšmë.

Atidžiai ištyrinëjus binariná medá, galima pastebëti, kad nagrinëjamo kodo, kai iš jo grážtama á viršûnê , perskaièiavimas á gretim¹ kod¹ reiklauja nagrinëti žemiau pateiktus keturis atvejus, priklausomai nuo g_i ir t reikšmës:

Šie pertvarkymai turi átakos vienetukø skaièiui tarp skilèiø : t reikšmê turime sumažinti 1, jei , ir padidinti 1, jei .

Pereinant prie gretimo kodo yra invertuojamos dvi skiltys:

skiltis ,

ir

Atlikus šiuos veiksmus, á stek¹ reikia árašyti papildom¹ informacij¹: tarpines viršûnes, esanèias tarp nagrinëjamos viršûnës ir nagrinëjamos kabanèios viršûnës. Kadangi tas priklauso nuo viršûnës steko viršuje, tai t reikšmë gali vël pasikeisti.

Jei arba , tai reiškia, kad viršûnë, kurioje mes esame, yra kabanti viršûnë: arba ir jokiø tarpiniø viršûniø saugoti nereikia. Šiuo atveju t visada lygus .

Kita vertus, jei ir , tai á stek¹ turime átraukti viršûnes , išskyrus t¹ atvejá, kai . Šiuo atveju á stek¹ átraukiame tik .

Parametro t reikšmë turi bûti perskaièiuojama. Kadangi tarp vienetukø gali bûti tik , tai . Be to, jei šiuo atveju t tampa lygus 0, tai .

Žemiau pateiktas deriniø generavimo minimalaus pokyèio tvarka algoritmas. Šiame algoritme stekas organizuojamas masyvu , o jo viršutinis elementas yra (žr. treèi¹já Grëjaus kodø generavimo algoritm¹). Kadangi , tai ekvivalentu, kad á stek¹ átraukiame .

const nn =

type mas = array [0..nn] of integer;

var n, i, k : integer;

g, tau : mas;

procedure der (n, k : integer);

var i, j, t : integer;

g, tau : mas;

begin

for j := 1 to k do

begin

g [j] := 1;

tau [j] := j + 1;

end

for j := k + 1 to n + 1 do

begin

g [j] := 0;

tau [j] := j + 1;

end

t := k;

tau [1] := k + 1;

i

while i <> n + 1 do

begin

writeln

for j := n downto 1 do write (g [j] : 3);

writeln

i := tau [1];

tau [1] := tau [i];

tau [i] := i + 1;

if g [i] = 1 then

begin

if t <> 0 then g[t]:=1-g[t]

else g[i-1]:=1-g[i-1];

t:=t+1;

end

else

begin

if t <> 1 then g [t – 1] := 1 – g [t – 1]

else g [i – 1] := 1 – g [i – 1];

t := t – 1;

end

g [i] :=1 – g [i];

if (t = i – 1) or (t = 0) then t := t + 1

else

begin

t := t – g [i – 1];

tau [i – 1] := tau [1];

if t = 0 then tau [1] := i – 1

else tau [1]:=t+1;

end

end

end

begin

writeln ('áveskite n');

readln (n);

writeln ('áveskite k');

readln (k);

der (n, k);

end

Atsitiktinio derinio generavimas

Aptarsime atsitiktinio poaibio, turinèio k elementø, iš aibës, turinèios n elementø , generavim¹. Aišku, kad tokio poaibio generavimo tikimybë yra .

Tam tikslui atsitiktinai parenkame vien¹ iš n elementø (pasirinkimo tikimybë ) ir po to atsitiktinai generuojame -elementá poaibá iš likusiø elementø.

Tada šios procedûros eigoje k-elemenèio poaibio išsirinkimo tikimybë yra tokiø tikimybiø sandauga:

P (pirmasis išsirinktas elementas – vienas iš k elementø

P (antrasis išsirinktas elementas – vienas iš k – 1 likusiø elementø)

_ _ __ _ _ __ _ _ __ _ _ __ _ _ __ _ _ _

P (k-asis išsirinktas elementas – paskutinysis iš likusiø elementø) .

Ši sandauga bus lygi:

Aptarsime atsitiktinio derinio generavimo algoritm¹.

Algoritmo realizavimui panaudosime papildom¹ masyv¹ p, kuriame saugosime dar neišrinktø elementø numerius. Po to, kai pirmieji elementai išsirinkti, tai bus s¹rašas elementø, kurie dar neišsirinkti. Kadangi nebûtina išsaugoti elementø tvark¹, tai, išsirinkus element¹ , , ájo viet¹ árašome neišsirinkt¹ element¹ .

Žemiau pateikiamas atsitiktinio derinio generavimo algoritmas.

begin

for j := 1 to n do p [j] := j;

R Æ

for j := 1 to k do

begin

r := rand (j, n);

R := R È

p [r] := p [j];

end

end

Këliniø generavimo algoritmai

Këliniø generavimo leksikografine tvarka algoritmas

Aptarsime këliniø iš n elementø generavimo leksikografine tvarka uždaviná. Sprêsdami šá uždaviná, laikysime aukšèiau pateiktos (žr. 3.4 paragrafo pradži¹) kombinatorinø objektø generavimo algoritmo struktûros. Norëdami išsiaiškinti šio algoritmo pagrindinius momentus, panagrinëkime pavyzdá, kai .

Pradinio kodo generavimas. Këliná talpinsime masyve , kurio elementai ir nusako këliná. Aišku, kad pradinis këlinys yra . Pavyzdžiu, jei , tai .

Paties mažiausio, leksikografiškai didesnio këlinio nei nagrinëjamas, apskaièiavimas. Tarkime, – nagrinëjamas këlinys. Pavyzdžiui, . Jei á këliná žiûrësime kaip á skaièiø, tai reikia rasti patá mažiausi¹ skaièiø, didesná nei nagrinëjamas. Tam tikslui reikia:

rasti pirm¹ iš dešinës por¹ toki¹, kad ,

rasti , t.y tarp elementø rasti patá mažiausi¹ element¹, didesná už ,

elementus ir sukeisti vietomis,

elementus (“uodeg¹”) surašyti atvirkšèia tvarka (“apversti”).

Pavyzdžiui, pirmoji iš dešinës pora, tenkinanti 1) punkto reikalavim¹, yra , o elementas . Tada, sukeitê 4 su 5, gausime . “Apvertê uodeg¹”, gausime patá mažiausi¹ leksikografiškai didesná këliná nei duotas: .

Generavimo pabaigos s¹lyga. Aišku, kad pats didžiausias këlinys yra (masyvo elementas yra pagalbinis, ir jo reikšmë lygi nuliui). Tada pirma iš dešinës pora , tenkinanti s¹lyg¹ yra . Kitaip tariant, jei , tai generavimo pabaiga.

Vadinasi, këliniø generavimo leksikografine tvarka algoritmas gali bûti užrašytas taip.

begin

fo i:= 0 to n do p [i] :=i;

t := true;

while t do

begin

spausdinti

i := n – 1;

while p [i] > p [i+ 1] do i := i – 1;

if i = 0 then t := false

else

begin

j := n;

while p [j] < p [i] do j := j – 1;

pp := p [i]; p [i] := p [j]; p [j] := pp;

k := i + 1; l := n;

while k < l do

begin

pp := p [k]; p [k] := p [l]; p [l] := pp;

k := k + 1; l := l – 1;

end

end

end

end

Këliniø generavimas antileksikografine tvarka

Be këliniø generavimo leksikografine tvarka naudojamas ir këliniø generavimo antileksikografine tvarka metodas.

Apibrëžimas. Vektorius yra antileksikografiškai mažesnis už vektoriø (žymime ), jei egzistuoja toks , kad , o , . Pastebësime, jei vietoje skaièiø paimtume raides , išdëstytas natûralia, pavyzdžiui, abëcëlës tvarka: , tai leksikografinë tvarka apibrëš n ilgio žodžiø išsidëstym¹ žodyne áprasta tvarka. Tuo tarpu antileksikografinë tvarka apibrëžia žodžiø tvark¹, kai tiek pozicijø eiliškumas sekoje, tie ir aibës elementø išsidëstymas žodyje yra atvirkšèias.

Pavyzdžiui, užrašykime aibës këlinius leksikografine ir antileksikografine tvarka.

Leksikografine tvarka:

1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 1, 2; 3, 2, 1.

Antileksikografine tvarka:

2, 1, 3; 1, 3, 2; 3, 1, 2; 2, 3, 1; 3, 2, 1.

Iš leksikografinës tvarkos këlinio 1, 3, 2 gausime antileksikografinës tvarkos këliná, jei 1-t¹ keisime 3-tu, 3-t¹ keisime 1-tu (imame aibës X elementus atvirkšèia tvarka) ir këlinio pozicijas surašome atvirkšèia tvarka. Gausime 3, 1, 2, o po to 2, 1, 3.

Këliniø generavimas antileksikografine didëjimo tvarka yra labai panašus á këliniø generavimo leksikografine didëjimo tvarka algoritm¹. Këliniø generavimui áveskime masyv¹ , kurio elementai apibrëžia nagrinëjam¹já këliná.

Pradinio këlinio generavimas. for i := 1 to n + 1 do p [i] := i;

Paties mažiausio antileksikografiškai didesnio këlinio apskaièiavimas. Tam tikslui reikia:

rasti pirm¹ iš kairës por¹ , toki¹, kad

rasti , t.y tarp elementø rasti patá didžiausi¹ element¹, mažesná nei ,

elementus ir sukeisti vietomis,

elementus surašyti atvirkšèia tvarka.

Generavimo pabaigos s¹lyga. Paskutinysis antileksikografinës tvarkos këlinys yra , o , t.y. masyvo elementai yra . Aišku, kad šiuo atveju pirmoji iš dešinës pora , tenkinanti 1)-ojo punkto reikalavim¹: , yra . Vadinasi, jei , tai generavimo pabaigos s¹lyga.

Pateiksime këliniø generavimo antileksikografine tvarka algoritm¹.

begin

fo i:= 0 to n + 1 do p [i] :=i;

t := true;

while t do

begin

spausdinti

i

while p [i-1] > p [i] do i := i + 1;

if i = n + 1 then t := false

else

begin

j

while p [j] > p [i] do j := j + 1;

pp := p [i]; p [i] := p [j]; p [j] := pp;

k := 1; l := i - 1;

while k < l do

begin

pp := p [k]; p [k] := p [l]; p [l] := pp;

k := k + 1; l := l – 1;

end

end

end

end

Kai , tai pateiktas algoritmas apskaièiuos këlinius:

Këliniø generavimas minimalaus pokyèio tvarka

Panagrinëkime këliniø generavimo minimalaus pokyèio tvarka metod¹ ir algoritm¹. Këliniø minimalaus pokyèio tvarka – tai tokia këliniø generavimo seka, kai bet kokie du gretimi këliniai skiriasi tik dviejø elementø padëtimi. Pavyzdžiui, kai , gautume sek¹: 1, 2, 3; 1, 3, 2; 3, 1, 2; 3, 2, 1; 2, 3, 1; 2, 1, 3.

Aptarsime këliniø generavimo tokia tvarka metod¹.

Kai , tai egzistuoja vienintelis këlinys: 1. Tarkime, kad turime këlinius, tenkinanèius minimalaus pokyèio tvark¹. Tada këliná generuosime taip.

Sunumeruokime visus këlinius numeriais nuo 1 iki . Tada, jei këlinio iš elemento numeris yra nelyginis skaièius, tai prie šio këlinio prirašykime element¹ n iš dešinës ir nuosekliai atlikime visus galimus to elemento postûmius á kairê. Jei këlinio iš elemento numeris yra lyginis, tai prie jo prirašykime element¹ n iš kairës ir nuosekliai atlikime visus galimus to elemento postûmius á dešinê.

Atlikê šiuos veiksmus, gausime këliniø minimalaus pokyèio sek¹ (žr. 3.4.2 pav.).

3.4.2 pav. Këlinø generavimas minimalaus pokyèio tvarka

Aptartas këliniø minimalaus pokyèio sekos generavimo metodas neatitinka aukšèiau pateiktos kombinatoriniø objektø generavimo algoritmo schemos: skaièiavimo eigoje reikia saugoti visus këlinius. Literatûroje [RND80] pateikta šio metodo realizacija, atitinkanti kombinatoriniø objektø generavimo algoritmo scem¹.

Aptarkime ši¹ realizacij¹.

Áveskime tris masyvus: , ir .

Masyvo p elementai apibrëš nagrinëjam¹ këliná. Elementai p₀ ir p_n+1 yra pagalbiniai elementai.

Masyvo a elementai nusako atvirkštiná këliná: a_k nurodo viet¹ (adres¹), kurioje masyve p yra elementas k. Kitaip tariant, . Masyvo d elementai apibrëžiami taip:

Këlinyje elementas i “stumiamas” iki jis pasiekia element¹, didesná už já patá. Tada yra keièiama šio elemento judëjimo kryptis ir bandoma “stumti” (jei galima) element¹ i – 1. Kadangi turime masyv¹ a, tai šis elementas lengvai randamas masyve p.

Tam, kad nutrauktume elemento n judëjim¹, á masyv¹ p ávesti du papildomi elementai ir , kuriø reikšmës yra lygios .

Elemento reikšmë yra lygi 0, nes p elemento, lygaus vienetui, judinti nereikia. Tai sekos generavimo pabaigos s¹lyga.

Këliniø generavimo minimalaus pokyèio tvarka algoritmas

begin

for i := 1 to n do begin

p [i] := i;

a [i] := i;

d [i] := –1;

end

d [1] := 0; p [0] := n + 1; p [n + 1] := n + 1; t := true;

while t do

begin

Spausdinti ();

m := n;

while p [a [m] + d [m]] > m do begin

d [m] := – d [m];

m := m – 1;

end

if m = 1 then t := false

else

begin

pp := p [a [m]];

p [a [m]] := p [a [m] + d [m]];

p [a [m] + d [m]] : =pp;

pp := a [m]; k := p [a [m]];

a [m] := a [k];

a [k] : =pp;

end

end

end

Kai , pateiktas algoritmas apskaièiuoja:

Atsitiktinio këlinio generavimas

Tarkime, kad – bet koks këlinys. Perskaièiuokime šá këliná pagal algoritm¹:

begin

for i := n downto 2 do

sukeisti p [i] su p [rand (1, i)],

èia rand k, l tolygiai pasiskirsèiusiø atsitiktiniø skaièiø iš atkarpos k, l generavimo procedûra

end

Taip gautas këlinys p su tikimybe gali sutapti su bet kuriuo këliniu iš visø këliniø aibës.

Tam, kad árodytume, jog visi këliniai vienodai galimi, pasinaudokime matematinës indukcijos metodu.

Kai – akivaizdu.

Tarkime, kad algoritmas generuoja atsitiktiná këliná, kai elementø skaièius yra . Tegu yra bet kuris aibës këlinys. Tada tikimybë, kad yra:

Aibës išskaidymas

n-elementës aibës X išskaidymas á k poaibiø (blokø) – tai aibës X poaibiø šeima , kurios elementai tenkina reikalavimus:

Poaibius vadinsime blokais.

Aibës X visø galimø išskaidymø á k blokus aibê žymësime , o aibës X visø galimø išskaidymø aibê žymësime . Aišku, kad

Su aibës X išskaidymu á blokus yra susijê Stirlingo ir Belo skaièiai.

Antrosios rûšies Stirlingo skaièius – tai skirtingø n-elementës aibës išskaidymo á k blokus skaièius, t.y.

èia .

Pavyzdžiui, , kadangi yra 7 skirtingi 4-iø elementø aibës išskaidymo á du blokus bûdai:

Akivaizdu, kad , kai . Be to, , kadangi tušèia blokø aibë sutinkamai su apibrëžimu yra tušèiosios aibës išskaidymas.

Su antrosios rûšies Stirlingo skaièiais, kaip ir su binominiais koeficientais, yra susijê daug tapatybiø.

Pirmiausia árodysime tapatybê, primenanèi¹ deriniø sudëties savybê, kuri yra susijusi su Paskalio trikampiu:

a)    , ,

b)   , ,  (3.4.2)

c)    , .

Formuliø ir teisingumas akivaizdus. 3.4.1 a) formulës teisingum¹ árodysime taip. Visus n-elementës aibës išskaidymus á k blokø suskirstykime á dvi klases. Pirmajai klasei priskirkime visus išskaidymus, kuriuse yra vienelementinis blokas , o antrajai klasei priskirkime visus išskaidymus, kai elementas n yra didesnio bloko (mažiausiai dviejø elementø aibës) elementas.

Aišku, kad pirmosios klasës galia yra , t.y. tokia, kokia yra aibës išskaidymo á blokus galia.

Antrosios klasës galia yra , kadangi prie kiekvieno išskaidymo á k blokus k skirtingais bûdais galima prijungti element¹ n: elementas n paeiliui jungiamas prie kiekvieno bloko.

(1.3.4) formulë ágalina lengvai apskaièiuoti . Žemiau pateikta reikšmiø lentelë, primenanti Paskalio trikampá.

Ši¹ lentelê galima traktuoti kaip “Stirlingo trikampá”. i-osios eilutës elementas yra lygus -osios eilutës elemento iš kairës ir -osios eilutës elemento iš viršaus, padauginto iš k, sumai.

6 lentelë. Antrosios rûšies Stirlingo skaièiai

Antrosios rûšies Stirlingo skaièiai yra susijê su n- osios eilës polinomo , užrašyto bazëje , užrašymu bazëje , èia

Teorema [Lip88]. Kiekvienam

Pavyzdžiui, .

Iš tikro,

Pirmosios rûšies Stirlingo skaièiai. Šie skaièiai žymimi ir jie yra koeficientai prie x laipsniø daugianaryje , t.y.

Kitaip tariant, skaièiai vaidina atvirkšèi¹ vaidmená atžvilgiu , t.y. leidžia polinom¹, užrašyt¹ bazëje pervesti á polinomo užraš¹ bazëje .

Nesunku parodyti (palyginant koeficientus prie laipsniø lygybëje ), kad tenkina s¹ryšius:

, ,

, ,  (3.4.3)

, .

Žemiau pateikta pirmosios rûšies Stirlingo skaièiø lentelë.

7 lentelë. Pirmosios rûšies Stirlingo skaièiai

Belo skaièius B_n. Belo skaièius – tai visø galimø n-elementës aibës X išskaidymo á blokus skaièius:

, èia .

Kitaip tariant,

Árodysime Belo skaièius siejantá rekurentiná s¹ryšá:

, .  (3.4.4)

Aibës visø galimø išskaidymø aibê galima išskaidyti á klases, priklausomai nuo bloko B, turinèio savyje element¹ , arba, kas ekvivalentu, priklausomai nuo aibës . Kiekvienai aibei egzistuoja tiksliai aibës X išskaidymø, turinèiø savyje blok¹ B. Grupuodami klases priklausomai nuo aibës galios, gauname (3.4.3) formulê.

Žemiau pateikta Belo skaièiø lentelë.

8 lentelë. Belo skaièiai

Aibës išskaidymo generavimo algoritmas

Aptarsime n-elementës aibës visø galimø išskaidymø generavimo algoritm¹. Šio algoritmo idëj¹ lengviausia paaiškinti suformulavus j¹ rekurentinëje formoje.

Aišku, kad kiekvienas aibës išskaidymas p vienareikšmiškai nusako aibës išskaidym¹ p_n , gaut¹ iš išskaidymo p, kai iš jo atitinkamo bloko pašalinamas elementas n (ir pašalinamas tušèiasis blokas, jei elementas n sudarë vienelementá blok¹).

Ir atvirkšèiai, jei turime aibës išskaidym¹ , tai lengva rasti visus aibës išskaidymus p, kad , t.y.

(3.4.5)

Ši savybë ágalina sudaryti paprast¹ rekurentiná metod¹, generuojantá visus galimus aibës išskaidymus: jei mes žinome aibës visø galimø išskaidymø s¹raš¹ L_n-1, tai visø galimø aibës išskaidymø s¹rašas L_n gaunamas pakeièiant kiekvien¹ s¹rašo L_n-1 išskaidym¹ s (3.4.5) seka. Be to, nesunku pastebëti, jei kas antram s¹rašo s¹rašo L_n-1 išskaidymui s invertuosime (rašysime atvirkšèia tvarka) (3.4.5) sek¹, tai s¹rašo L_n gretimi išskaidymai mažai skirsis vienas nuo kito. Tiksliau kalbant, kiekvienas gretimas s¹rašo L_n išskaidymas bus gautas iš prieš já esanèio išskaidymo pašalinant kažkoká element¹ iš kažkurio bloko ir patalpinant šá element¹ á kit¹ blok¹, arba sukuriant iš jo vienelementiná blok¹. Pavyzdžiui, jei , tai gausime tokius s¹rašus:

Toliau aptarsime nerekurentinê šio metodo realizacij¹.

Aibës išskaidymo blokus surašysime jø mažiausio elemento didëjimo tvarka. Bloko mažiausi¹ element¹ mes vadinsime bloko numeriu. Reikia pažymëti, kad gretimø blokø numeriai bendru atveju nëra iš eilës ein¹ natûralieji skaièiai.

Šiame algoritme naudosime kintamuosius ir , , atitinkamai reiškianèius prieš ir po bloko, kurio numeris i, stovinèiø blokø numerius. Jei blokas, kurio numeris i, yra paskutinysis išskaidymo blokas, tai .

Naudosime kintam¹já , . Jei , tai reiškia, kad i-tasis aibës elementas priklauso blokui, kurio numeris k.

Elemento judëjimo kryptá nusakys kintamasis , . Jei , tai elementas i “juda” pirmyn.

Žemiau pateiktas algoritmas generuoja visus galimus aibës išskaidymo bûdus, kai duotas aibës elementø skaièius n. Algoritmo rezultatas: visø galimø aibës išskaidymø seka, kurioje kiekvienas išskaidymas gaunamas iš prieš tai buvusio, perkeliant vienintelá element¹ á kit¹ blok¹.

begin

for i := 1 to n do

begin

blok [i] := 1; pirmyn [i] := true;

end

sek

Atspausdinti išskaidym¹

elementai, masyve blok pažymëti tuo paèiu numeriu k,

priklauso k-ajam blokui.

j := n;

while j > 1 do

begin

k := blok [j];

if pirmyn [j] then

begin

if sek [k] := 0 then

begin

sek [k] := j; prec [j] := k; sek [j] := 0;

end

if sek [k] > j

begin

prec [j] := k;

sek [j] := sek [k];

prec [sek [j]] := j; sek [k] := j;

end

blok [j] := sek [k]

end

else

begin

blok [j] := prec [k];

if k = j then

if sek [k] = 0 then sek [prec [k]] := 0;

else

begin

sek [prec [k]] := sek [k];

prec [sek [k]] := prec [k];

end

end

Atspausdinti išskaidym¹.

j := n;

while ((j > 1) and ((pirmyn [j]) and (blok [j] = j))

or ((not pirmyn [j]) and (blok [j] := 1))) do

begin

pirmyn [j] := not pirmyn [j];

j := j – 1;

end

end

end

Pateiktas algoritmas pradžioje generuoja išskaidym¹ , t.y. pirm¹já aibës išskaidym¹ s¹raše L_n, kuris gaunamas aukšèiau aprašytu rekurentiniu metodu.

Pagrindinio ciklo “while j > 1 do” paskirtis yra “aktyvaus” elemento j radimas ir jo perkëlimas á kaimyniná blok¹, t.y. á blok¹ iš dešinës, jei pirmyn [j] turi reikšmê true (šiuo atveju gali bûti sukuriamas blokas ), ir á blok¹ iš kairës, jei pirmyn [j] = false.

Iš aukšèiau pateikto rekurentinio metodo išplaukia, kad elementas j gali bûti “judinamas”, kai visi didesni už já elementai pasiekia savo ribinê kairi¹j¹ arba dešini¹j¹ padëtá. Kitaip tariant, “aktyvusis elementas” j* yra toks elementas, kai visi didesni už já elementai j (j > j*) tenkina vien¹ iš dviejø s¹lygø:

a)      pirmyn [j] and (blok [j] = j), t.y. elementas juda pirmyn (á dešinê) ir pasiekia savo dešini¹j¹ ribinê padëtá (aišku, kad j negali bûti elementu bloko, kurio mažiausias elementas yra didesnis už j);

b)      not pirmyn [j] and (blok [j] = 1), t.y. elementas juda atgal (á kairê) ir pasiekia savo kairi¹j¹ ribinê padëtá.

Aišku, kad, jei elementas j tenkina vien¹ iš minëtø s¹lygø, tai keièiama jo judëjimo kryptis.

Paanalizuokime “aktyvaus” elemento perkëlimo á kit¹ blok¹ proces¹.

Pirmiausia randamas numeris bloko, kuriame yra aktyvusis elementas. Tarkime, kad tokio bloko numeris yra k.

Jei “aktyvusis” elementas “juda” á dešinê, tai pakanka perkelti já á blok¹, kurio numeris yra , jei ir .

Jei arba , tai pirmiausia reikia modifikuoti reikšmê.

Tarkime, sek [k]  . Vadinasi, “aktyviojo” elemento blokas yra paskutinysis išskaidymo blokas. Šiuo atveju bus sudaromas naujas blokas . Tam tikslui pakanka priimti: ir atitinkamai pakeisti ir reikšmes (žr. algoritmo tekst¹).

Tarkime, sek [k] > j. Tai reiškia, kad visi blokai, esantys dešiniau bloko k, sudaryti iš elementø, didesniø nei j (visi tie elementai užima ribinê dešinê padëtá). Vadinasi, (žr. rekurentiná metod¹), šiuo atveju reikia sukurti vienelementá blok¹ . Tai ir ávykdoma (žr. algoritmo tekst¹).

Situacijoje, kai “aktyvusis” elementas juda atgal (á kairê), pakanka patalpinti šá element¹ á prieš blok¹ k stovintá blok¹ ir atlikti atitinkamus masyvø sek ir prec elementø pakeitimus.

Žemiau surašyti visi galimi aibës išskaidymo bûdai, apskaièiuoti pagal aukšèiau pateikt¹ algoritm¹.

Aišku, kad išskaidymø skaièius yra

Sveikøjø skaièiø kompozicija ir išskaidymas

Nagrinësime natûraliojo skaièiaus n išskaidym¹ á neneigiamø sveikøjø skaièiø sek¹, kad .

Jei skaièiø tvarka sekoje yra svarbi, tai toks skaièiaus n išskaidymas vadinamas kompozicija. Šiuo atveju paprastai ávedamas apribojimas: , .

Jei skaièiø tvarka nesvarbi ir , tai yra multiaibë (aibë su pasikartojanèiais elementais) ir vadinama skaièiaus n išskaidymu.

Pavyzdžiui, jei , tai (3), (1, 2), (2, 1), (1, 1, 1) yra skaièiaus 3 kompozicija, o (3), (1, 2), (1, 1, 1) – išskaidymas.

Kompozicija

Nagrinëjant kompozicij¹, á skaièiø n patogu žiûrëti kaip á atkarp¹, sudaryt¹ iš vienetinio ilgio atkarpëliø, ir atkarpëliø susijungimo vietos pažymëtos taškais.

Pavyzdžiui, kai , turësime (žr. 3.4.2 pav.).

3.4.2 pav. Grafinis kompozicijos (2, 1, 2, 2, 1) vaizdavimas

Tada kompozicijos elementai yra atstumas tarp gretimø pažymëtø taškø. 3.4.2 pav. pavaizduota skaièiaus kompozicija (2, 1, 2, 2, 1). Aišku, kad kiekvien¹ kompozicij¹ galima vaizduoti dvejetainiu skaièiumi, turinèiu skiltá: vienetinë skiltis rodo pažymët¹ tašk¹. Pavyzdžiui, kompozicijos (2, 1, 2, 2, 1) kodas yra .

n skaièiaus kompozicija, susidedanti iš k daliø, atitinka -skiltá dvejetainá skaièiø, turintá vienetuk¹, ir todël egzistuoja tokiø kompozicijø.

Išskaidymas

Išskaidymas skiriasi nuo kompozicijos tuo, kad komponentø tvarka nesvarbi. Pavyzdžiui, išskaidymo atveju nedarome skirtumo tarp tokiø skaièiaus 4 išskaidymø: , , . Nagrinëjant skaièiaus n išskaidym¹, patogu komponentes išdëstyti didëjimo tvarka, t.y. .

Skaièiaus n išskaidym¹ á l komponentes patogu generuoti leksikografine tvarka, pradedant išskaidymu , , ir têsiant proces¹ tokiu bûdu: norëdami gauti leksikografiškai didesná išskaidym¹ nei nagrinëjamas, nagrinëjame elementus iš dešinës á kairê iki rasime pirm¹já element¹ , tenkinantá s¹lyg¹ ; po to keièiame visiems , ir elementui p_l suteikiame reikšmê .

Pavyzdžiui, jei , ir nagrinëjame išskaidym¹ , tai gausime, kad pirmasis iš dešinës vienetukas tenkina s¹lyg¹ . Todël kitas išskaidymas bus .

Jei nei vienas išskaidymo elementas netenkina s¹lygos , tai generavimo procedûra baigiama.

Žemiau pateikiamas aptarto metodo algoritmas.

Skaièiaus n išskaidymø generavimo leksikografine tvarka algoritmas

begin

l

p [1] := n;

p

while l £ n do

begin

spausdinti

i := l – 1;

while p [l] – p [i] < 2 do i := i – 1;

if i ¹ 0 then for j := i to l – 1 do p [j] := p [i] + 1

else

begin

for j := 1 to l do p [j] := 1;

l := l + 1:

end

end

end

Skaièiaus n išskaidymo algoritm¹ galima iš esmës pagerinti. Skaièiaus n išskaidym¹ galima užrašyti taip:

èia rodo, kad komponentë á išskaidym¹ áeina kartø, t.y.

Pasinaudojant tokiu išskaidymo užrašymu ir generuojant išskaidymus taip, kad , galima gauti efektyvesná išskaidymø generavimo algoritm¹ nei aukšèiau pateiktas.

Pavyzdžiui, kai , generuodami išskaidymus nurodyta tvarka, gausime toki¹ išskaidymø sek¹:

Žemiau pateiktame algoritme skaièiaus n išskaidym¹ pradësime nuo išskaidymo . Norëdami gauti nagrinëjamam išskaidymui gretim¹ išskaidym¹, nagrinësime patá dešinájá išskaidymo element¹ .

Jei , tai galime pašalinti du elementus ir ávesti dar vien¹ element¹ (arba ávesti vien¹ element¹ , jei tokio elemento nagrinëjamu momentu nebuvo).

Jei , tai suma pakankamai didelë, kad galëtume ávesti dar vien¹ . Bet kuriuo atveju tas, kas lieka, paverèiama á atitinkam¹ vienetukø skaièiø.

Skaièiaus n išskaidymø generavimo “žodyno” tvarka algoritmas

begin

l

p [–1] := 0; m [–1] := 0;

p [0] := n + 1;

m

p

m [1] := n;

while l ¹ 0 do

begin

spausdinti

sum := m [l] * p [l];

if m [l] = 1 then

begin

l := l – 1

sum := sum + m [l] * p [l];

end

if p [l – 1] = p [l] + 1 then

begin

l := l – 1;

m [l] := m [l] + 1

end

else

begin

p [l] := p [l] + 1;

m [l] := 1;

end

if sum > p [l] then

begin

p [l + 1] := 1;

m [l + 1] := sum – p [l];

l := l + 1

end

end

end

Aišku, kad pateiktas algoritmas yra tiesinis, kadangi skaièius operacijø, reikalingø pereinant nuo vieno išskaidymo prie kito, yra apribotas konstanta, nepriklausanèia nei nuo n, nei nuo l.