How can I write a program to generate all partitions of a set?

Do you want to generate all subsets, or all partitions?

Come up with some order for the set. Going from first element to the next to last, either include just the element or include the element followed by a partition symbol. The last element is always included without a partition symbol after it. That gives the 2^(n-1) partitions. Writing a recursive program to do that should be fairly straightforward.

Something like this:

Subsets(Old, New)
{
If New is empty
print Old
Else
{
x = first element of New
Subsets(Old, New – x)
Subsets(Old + x, New – x)
}
}

Subsets(Empty Set, Original Set)

Urgh, tabbing not working. Oh well, its not too hard to figure out anyway.

I did mean all partitions; I’ve already written a generator for subsets. I’d like to thank everyone for their help…I’m feeling so great now that I’ve figured out a solution. You guys helped me get thinking in the right direction…I am forever indebted :)