Blatt 9 SS00

Prof. Laue

Abgabe 05.07.2000
 
 
 
 
 

Aufgabe 12 (3+3+4+4) Mengenpartition , restricted growth function
 

In der Vorlesung wurde die Bijektion zwischen Mengenpartition und restricted growth functions (RGF) erwähnt.

a) Geben Sie in Pseudocode einen Algorithmus an, der zu einer Mengenpartition die RGF berechnet.
b) Geben Sie in Pseudocode einen Algorithmus an, der zu einer RGF die Mengenpartition berechnet.

c) Geben Sie in Pseudocode einen Algorithmus  "next set partition" an. Eingabe ist eine Mengenpartition (oder RGF), diese soll modifiziert werden. Durch wiederholten Aufruf  sollen so alle Mengenpartitionen zu einer n-Menge durchlaufen werden.
d) Implementieren Sie c) und bestimmen Sie mittels Ihrer Routine die 8-te Bellzahl.