Richard F.L.R.Snashall wrote:

> (E-Mail Removed) wrote:

>

>> Given a set {A,B,C,D}, I want to generate all possible partitions of

>> this set into two subsets, i.e. ({A},{B,C,D}) ({B},{A,C,D})

>> ({C},{A,B,D}) ({D},{A,B,C}) ({A,B},{C,D}) ({A,C},{B,D}) ({A,D},{B,C}).

>> If I generate all subsets of {A,B,C,D} and their complements, then all

>> of these partitions will be generated twice (e.g, the first partition

>> will be generated as the result of using {A} and its complement, and

>> then as the result of using {B,C,D} and its complement). That is why I

>> was asking for a more efficient algorithm to do this.

>> Yes, I need all partitions, divided sets are not going to be large, on

>> average they should not exceed than 5-7 elements.

>> Thanks for all your replies, Mikolaj

>>

> Maybe you can consider only those subsets with order less than or equal

> in order to half the order of the original set. This would at least

> reduce the duplication complication to the smaller instance of those

> sets with even order and subsets of exactly half the order. For tha

> case maybe you could consider only those subsets which contain a

> particular [first] element. Just a thought...
Or you could consider all subsets containing a particular element, and

their complements. For a fixed element x, each complementary pair will

contain a set containing x and a set not containing x.

It sounds as though the OP already knows how to generate all subsets of

a given set. Set aside one element, e.g. A. Generate all subsets of the

remainder after deleting A from the set. Each of those sets and its

complement relative to the original set is a partition, and each

partition will only be generated once.

Patricia