A week ago I posted a question concering partitioning a set. Here comes
the solution. Beyond what Tom Kramer had already posted there are two
other ways:
1) Non-deterministic extension of Lisp
proposed by Jeffrey Mark Siskind
If you use Screamer, a non-deterministic add-on which allows backtracking
(and much more), there is a very simple way to write such a function. One
can even find the function in the documentation distributed with Screamer.
(For more info on Screamer, look at the FAQ).
2) Restricted Growth Functions
proposed by Rich Evans
My problem is known and solved in combinatorics. There is a special type
of functions, called restricted growth functions. Enumerating them is very
easy and there is a bijection between an rgf and a partition that natural,
that in most cases you don't even need to calculate the partition
corresponding to the rgf. For more information, consult the book
"Constructive Combinatorics" by Dennis Stanton & Dennis White (Springer-
Verlag 1986).
I'd like to thank Robert St. Amant, Rich Evans, Tom Kramer, John Krieger,
Jeff Siskind and Sampath Srinivas for their help and suggestions.
Stephan.
--
Stephan Kepser ······@cis.uni-muenchen.de
CIS Centrum fuer Informations- und Sprachverarbeitung
LMU Muenchen, Wagmuellerstr. 23/III, D-80538 Muenchen, Germany
Tel: +49 +89/2110666 Fax: +49 +89/2110674