6. óra
Még mindig nincs vége a kombinatorikának: jönnek a partíciók.
Partíciók
Beszélhetünk pozitív egészek partícióiról és halmazok partícióiról. Az első esetben az n pozitív egész számot kell minden lehetséges módon pozitív egészek összegére bontani. A 4 szám partíciói:
1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4
A második esetben egy n elemű halmaz nemüres halmazok diszjunkt uniójára való felbontásait keressük. Az {1, 2, 3, 4} halmaz partíciói:
$
\{1,2,3,4\} = \{1,2,3\}\cup\{4\} = \{1,2,4\}\cup\{3\} =
\{1,3,4\}\cup{2} = \{2,3,4\}\cup\{1\} = \{1,2\}\cup\{3,4\}
= \{1,3\}\cup\{2,4\} =
$
$
=\{1,4\}\cup\{2,3\} = \{1,2\}\cup\{3\}\cup\{4\} = \{1,3\}\cup\{2\}\cup\{4\} = \{1,4\}\cup\{2\}\cup\{3\}
= \{2,3\}\cup\{1\}\cup\{4\} =
$
$
=\{2,4\}\cup\{1\}\cup\{3\} = \{3,4\}\cup\{1\}\cup\{2\} = \{1\}\cup\{2\}\cup\{3\}\cup\{4\}
$
Egyik esetben sem ismert zárt formula a partíciók számára, de létezik (komoly) matematikai apparátus a darabszám meghatározására. (Generátorfüggvények, másodfajú Stirling-számok.)
Egész számok partíciói - rekurzív módszer
par(n,m)
Ha n = 0 akkor az a[1],a[2],...,a[m] partíció bejárása
különben
Ciklus i := a[m]-től n-ig
a[m+1] := i
par(n - i, m + 1)
Ciklus vége
Elágazás vége
Eljárás vége
Egész számok partíciói - iteratív módszer
Egyszerű iteratív algoritmus adódik a partíciók fordított lexikografikus sorrendben történő bejárásából. Például az 5 partíciói (elhagyva a + jeleket):
5, 41, 32, 311, 221, 2111, 11111
Ha egy partíció nem csupa 1-ből áll, akkor a sorozat vége (x + 1) és néhány 1-es, valamilyen
x $\ge$ 1 számmal. Ekkor a sorrendben következő partíciót úgy kapjuk, hogy az (x + 1)1...1 végződést helyettesítjük az x...xr végződéssel, a megfelelő r $\le$x értékkel.
A programban q tárolja a legnagyobb olyan indexet, melyre a[q]$\ne$1.
a[0] := 0; m := 1
Ciklus
a[m] := n
Ha n = 1 akkor q := m - 1 különben q := m
az a[1],a[2],...,a[m] partíció bejárása
Ciklus amíg a[q] = 2
a[q] := 1; q := q - 1; m := m + 1; a[m] := 1
az a[1],a[2],...,a[m] partíció bejárása
Ciklus vége
Ha a[q] = 0 akkor kilépés a főciklusból
x := a[q] - 1; a[q] := x; n := m – q + 1; m := q + 1
Ciklus amíg n > x
a[m] := x; m := m + 1; n := n - x
Ciklus vége
Ciklus vége
Halmazok partíciói
Később...
Feladat
