6. óra - Partíció
Elmélet > Algoritmusok > Kombinatorikai algoritmusok
Címkék > Óra

6. óra

(2008.10.21.)

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

Indítás:

par(n,0)

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

Bolgár szoliter