Generating all partitions of a set

Discussion in 'Java' started by megaduks@tlen.pl, Sep 4, 2005.

  1. Guest

    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
    , Sep 4, 2005
    #1
    1. Advertising

  2. 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/
    Thomas Hawtin, Sep 4, 2005
    #2
    1. Advertising

  3. Guest

    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
    , Sep 4, 2005
    #3
  4. 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...
    Richard F.L.R.Snashall, Sep 4, 2005
    #4
  5. Richard F.L.R.Snashall wrote:
    > 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
    Patricia Shanahan, Sep 4, 2005
    #5
  6. Roedy Green Guest

    On 4 Sep 2005 11:59:00 -0700, 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.
    Roedy Green, Sep 4, 2005
    #6
  7. Patricia Shanahan wrote:
    >
    >> 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/
    Thomas Hawtin, Sep 5, 2005
    #7
  8. Roedy Green Guest

    On Mon, 05 Sep 2005 00:51:39 +0100, Thomas Hawtin
    <> 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.
    Roedy Green, Sep 5, 2005
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    11
    Views:
    6,402
    Luc The Perverse
    Nov 19, 2005
  2. Frank Bechmann
    Replies:
    3
    Views:
    325
    Frank Bechmann
    Nov 9, 2003
  3. Steve
    Replies:
    7
    Views:
    339
    Anton Vredegoor
    Apr 30, 2004
  4. Nick J Chackowsky

    Partitions of an integer

    Nick J Chackowsky, Jul 24, 2004, in forum: Python
    Replies:
    5
    Views:
    540
    Damien Wyart
    Jul 26, 2004
  5. joblack
    Replies:
    0
    Views:
    242
    joblack
    May 3, 2012
Loading...

Share This Page