7. óra
A beígért folytatás...
Halmazok partíciói
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\}
$
Partíció generáló algoritmus
Egy véges $\{1, 2, \ldots, n\}$ halmaz minden partícióija egyértelműen kódolható egy olyan $a_1, a_2,\ldots, a_n$ sorozattal,
melyre
$a_1 = 0, a_{j+1} \le 1 + max(a_1, \ldots, a_j) $ $ (1 \le j < n)$,
ahol
$a_j = a_k$ akkor és csak akkor teljesül,
ha $j$ és $k$ ugyanabba a részhalmazba esik,
továbbá $a_j~ $ a lehető legkisebb értéket kapja, amikor $j$ a legkisebb szám részhalmazában.
Például $n = 4$-re az alábbi kódolást kapjuk:
| partíció |
kód |
|
Partíció |
kód |
| {1234} |
0000 |
|
{14}{23} |
0110 |
| {123}{4} |
0001 |
|
{1}{234} |
0111 |
| {124}{3} |
0010 |
|
{1}{23}{4} |
0112 |
| {12}{34} |
0011 |
|
{14}{2}{3} |
0120 |
| {12}{3}{4} |
0012 |
|
{1}{24}{3} |
0121 |
| {134}{2} |
0100 |
|
{1}{2}{34} |
0122 |
| {13}{24} |
0101 |
|
{1}{2}{3}{4} |
0123 |
| {13}{2}{4} |
0102 |
|
|
|
Az algoritmus a $b_1,\ldots,b_n$ változók használatával generálja a partíciók kódjait, ahol $b_{j+1} = 1+\max(a_1, \ldots, a_j)$.
Ciklus i := 1-től n-ig
a[i] := 0; b[i]:=1
Ciklus vége
Ciklus
az a[1],...,a[n] által kódolt partíció bejárása
Ciklus amíg a[n] <> b[n]
a[n]:=a[n]+1
az a[1],...,a[n] által kódolt partíció bejárása
Ciklus vége
j := n-1
Ciklus amíg a[j]=b[j]
j:=j-1
Ciklus vége
Ha j = 1 akkor kilépés a főciklusból
a[j]:=a[j]+1
Ha a[j]=b[j] akkor b[n]:= b[j]+1 különben b[n]:= b[j]
j:=j+1
Ciklus amíg j < n
a[j]:=0; b[j] := b[n]; j:=j+1
Ciklus vége
a[n] := 0
Ciklus vége
A C1 ciklus a kód utolsó elemét növeli, amíg lehet. Ha elérte a maximumot, a C2 ciklusban keresünk egy még növelhető elemet. Ha találunk ilyet, megnöveljük, és a mögötte lévő kódrész elemeit lenullázzuk.
$n = 3$-ra a következő sorrendben kapjuk meg a partíciók kódját:
000, 001, 010, 011, 012,
Partíciók száma
| halmaz elemszáma | partíciók száma |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 15 |
| 5 | 52 |
| 6 | 203 |
| 7 | 877 |
| 8 | 4140 |
| 9 | 2114 |
| 10 | 115975 |
| 11 | 678570 |
| 12 | 4213597 |
| 13 | 27644437 |
| 14 | 190899322 |
| 15 | 1382958545 |
| 16 | 10480142147 |
| 17 | 82864869804 |
| 18 | 682076806159 |
| 19 | 5832742205057 |
| 20 | 51724158235372 |
| 21 | 474869816156751 |
| 22 | 4506715738447323 |
Feladat
