Generating all partitions of a set

[megaduks]

Hello everyone,
I'm struggling with the following problem. I have a set (implemented as
a TreeSet, but this can be easily changed). I want to generate all
possible partitions of this set into two disjoint subsets. Of course, I
can generate all subsets of a given set and then use a subset along
with its complement, but this approach generates every partition twice.
Is there a better and more efficient way? Maybe a utility class? I'll
be grateful for all hints and remarks.
Best regards, Mikolaj

 

[Thomas Hawtin]

I'm struggling with the following problem. I have a set (implemented as
a TreeSet, but this can be easily changed). I want to generate all
possible partitions of this set into two disjoint subsets. Of course, I
can generate all subsets of a given set and then use a subset along
with its complement, but this approach generates every partition twice.
Is there a better and more efficient way? Maybe a utility class? I'll
be grateful for all hints and remarks.

You essentially want a set of all subsets? You do know that there are
2^n of them? Are you sure (y/n)?

To pair up each subset with its complement think of a subset as a binary
number with as many digits as the set has elements. The subset of
subsets with the top bit set/contains the first element is the
complement of the subset of subsets with the top bit clear/doesn't
contain the first element. The complement of a subset is the subset
whose binary representation is the complement of the first subset.

It isn't going to be efficient. If you really have to go through all
combinations, it'll probably be better to create the subsets on demand.

Tom Hawtin

 

[megaduks]

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

 

[Richard F.L.R.Snashall]

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...

 

[Patricia Shanahan]

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

 

[Roedy Green]

I want to generate all
possible partitions of this set into two disjoint subsets.

See http://mindprod.com/jgloss/combination.html

let us say you had 4 elements in your set. You can map the binary
numbers 0000 .. 1111 to all possible subsets.

You can map the numbers 000 ... 111 to all possible splittings.
All you are doing is taking one element out of the game and
arbitrarily putting it the first camp.

 

[Thomas Hawtin]

It sounds as though the OP already knows how to generate all subsets of
a given set. [...]

Only megaduks has 14 subsets instead of 2^4. The complete set and the
empty set ({A, B, C, D} and {}) are missing. Assuming we are allowing
improper subsets.


If you are creating loads of these sets it may be taking an approach
similar to 5.0's EnumSet.

For efficiency don't keep some structure of actual object. Instead
assign a number (an ordinal) to each element. The set can then be
represented by a nice, compact bit set. Don't use boolean[] as that will
take eight times too much memory, on any sane Java implementation on
typical hardware.

Tom Hawtin

 

[Roedy Green]

For efficiency don't keep some structure of actual object. Instead
assign a number (an ordinal) to each element. The set can then be
represented by a nice, compact bit set. Don't use boolean[] as that will
take eight times too much memory, on any sane Java implementation on
typical hardware.

for 64 elts or less, a long will do fine. For more a
java.util.BitSet.