Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Generating all partitions of a set

Reply
Thread Tools

Generating all partitions of a set

 
 
megaduks@tlen.pl
Guest
Posts: n/a
 
      09-04-2005
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

 
Reply With Quote
 
 
 
 
Thomas Hawtin
Guest
Posts: n/a
 
      09-04-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> 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
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
 
 
 
megaduks@tlen.pl
Guest
Posts: n/a
 
      09-04-2005
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

 
Reply With Quote
 
Richard F.L.R.Snashall
Guest
Posts: n/a
 
      09-04-2005
(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...
 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      09-04-2005
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
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      09-04-2005
On 4 Sep 2005 11:59:00 -0700, (E-Mail Removed) wrote or quoted :

>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.
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Again taking new Java programming contracts.
 
Reply With Quote
 
Thomas Hawtin
Guest
Posts: n/a
 
      09-04-2005
Patricia Shanahan 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}).

>
> 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
--
Unemployed English Java programmer
http://jroller.com/page/tackline/
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      09-05-2005
On Mon, 05 Sep 2005 00:51:39 +0100, Thomas Hawtin
<(E-Mail Removed)> wrote or quoted :

>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.
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Again taking new Java programming contracts.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Problems to list *all* mountedwindows partitions joblack Python 0 05-03-2012 03:57 PM
generating unique set of dicts from a list of dicts bruce Python 0 01-10-2012 08:24 PM
I used to have 7 partitions, all of a sudden I have 14. Sigh. thanatoid Computer Support 30 12-02-2008 02:45 AM
There was an error generating the XML document. --> Object reference not set to an instance of an object fraser.elder@gmail.com ASP .Net Web Services 1 12-01-2005 11:21 PM
Diskeeper not showing all partitions ... Ronnie Davis Computer Support 4 12-27-2004 12:55 PM



Advertisments