Re: Help on Partitions, Again!!! (fwd)

• To: mathgroup at smc.vnet.net
• Subject: [mg24658] Re: [mg24636] Help on Partitions, Again!!! (fwd)
• From: Rob Pratt <rpratt at email.unc.edu>
• Date: Mon, 31 Jul 2000 09:23:26 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Addendum to my previous response:

Of course, the procedure I outlined will return both
{{A,B,C},{D,E,F}} and {{D,E,F},{A,B,C}} as two different objects.  If you
consider these to be the same object, you could then map Sort to the
resulting pairs and then apply Union to eliminate duplicates.  Or you
could use Union with an appropriate SameTest.  (The original procedure
produces 20 partitions, but I believe you only wanted 10.)

But a more efficient approach would be to remove A from the original list
and run the procedure on {B,C,D,E,F}, with the convention that the element
A belongs to the first set in each pair.  You could explicitly add in A as
a final step.

Also, if the two parameters add up to something less than the length of
the list (such as 2 + 1 < 6), you could just apply the procedure to each
subset of the appropriate size (such as 2 + 1 = 3).  This is not overkill,
as there will be no duplicates.

Perhaps the best approach would be to look at the code used to define
KSubsets and doctor it to suit your needs.  Steven Skiena's book
Implementing Discrete Mathematics describes the algorithms and code for
the Combinatorica package (which he wrote).

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/

---------- Forwarded message ----------
From: Rob Pratt <rpratt at email.unc.edu>
To: mathgroup at smc.vnet.net
Subject: [mg24658] Re: [mg24636] Help on Partitions, Again!!!

Jose,

If the two parameters will always add up to the length of the list (as in
your example with 3 + 3 = 6), you can use KSubsets in the Combinatorica
package.  Just ask for the complement along with each subset.  More
explicitly, use KSubsets[{A,B,C,D,E,F},3], then map
Complement[{A,B,C,D,E,F},#]& to the result, then combine the two lists in
pairs with Transpose[{lis1,lis2}].

Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill

rpratt at email.unc.edu

http://www.unc.edu/~rpratt/

On Fri, 28 Jul 2000, Jose Prado de Melo wrote:

>
>
> Hello, MathGroup
> First of all, thanks for your attention.
> To be more specific:
> It's not too dificult to calculate the solution of the problem:
> How many ways, can the set {A,B,C,D,E,F} be separeted into two parts
> with three elements in each?
>  Answer:   x = 6!/(2!.3!.3!) = 10
>  I'm looking for a function to generate all the partitions using
> Mathematica 3.0 .
> I'm not sure, but I think the package Combinatorica doesn't have a
> function to do this.
> For example, I'm trying to think up a function f  like this one:
>
> In[ ] = f [ {A,B,C,D,E,F},{3,3}]
> Out [ ] = { { {A,B,C},{D,E,F} }, { {
> A,B,F},{C,D,E}},...................} and so on.
> In [ ] = Length[%]
> Out [ ] = 10
>