Re: Re: Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34552] Re: [mg34440] Re: Re: [mg34432] Help! How to calculate additive partitions?
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Mon, 27 May 2002 01:16:57 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On Mon, 20 May 2002 BobHanlon at aol.com wrote:
> A much faster way came to mind:
>
> Needs["DiscreteMath`Combinatorica`"];
>
> myPartitions[n_Integer?Positive] :=
>
> Flatten[Permutations /@ Partitions[n],1]
>
> n=5;
> myPartitions1[n]
>
> {{5}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {1, 1, 3}, {1, 2, 2},
>
> {1, 3, 1}, {2, 1, 2}, {2, 2, 1}, {3, 1, 1}, {1, 1, 1, 2},
>
> {1, 1, 2, 1}, {1, 2, 1, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}}
>
> Length[%]==2^(n-1)
>
> True
>
>
> In a message dated 5/19/02 12:01:55 PM, writes:
>
> >In a message dated 5/19/02 5:08:45 AM, Tom.Brodhead at worldnet.att.net writes:
> >
> >>I need to find a formula or method that will allow me to calculate the
> >>additive partitions of a given number.
> >>
> >>E.g., 3 can be expressed as
> >>
> >>1+1+1
> >>2+1
> >>1+2
> >>3
> >>
> >>IMPORTANT: Even though 2+1 and 1+2 employ the same values, the order is
> >>important and thus the procedure or formula that I need would need to
> >>produce both of those results.
> >>
> >>Likewise, 4 would break down this way:
> >>1+1+1+1
> >>2+1+1
> >>1+2+1
> >>1+1+2
> >>2+2
> >>3+1
> >>1+3
> >>4
> >>
> >>I need to calculate both the number of results that I should get, and
> >the
> >>results themselves.
> >>
> >>How can this be done?
> >>
> >
> >Needs["DiscreteMath`Combinatorica`"];
> >
> >
> >A brute force approach which gets quite slow for large n:
> >
> >
> >myPartitions[n_Integer?Positive] :=
> >
> > Union[Flatten[Table[Compositions[n,k],{k,n}],1] //.
> >
> > {x___,0,y___}:> {x,y}];
> >
> >
> >myPartitions[3]
> >
> >
> >{{3}, {1, 2}, {2, 1}, {1, 1, 1}}
> >
> >
> >myPartitions[4]
> >
> >
> >{{4}, {1, 3}, {2, 2}, {3, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 1, 1,
> >1}}
> >
> >
> >The number of results for myPartitions[n] is just 2^(n-1)
> >
> >
> >Table[{n,l=Length[myPartitions[n]], l==2^(n-1)}, {n,7}]
> >
> >
> >{{1, 1, True}, {2, 2, True}, {3, 4, True}, {4, 8, True},
> > {5, 16, True}, {6, 32, True}, {7, 64, True}}
> >
> >
> >numberOfMyPartitions[n_Integer?Positive] := 2^(n-1);
> >
>
> Bob Hanlon
> Chantilly, VA USA
We get a method that's even faster than Bob's by speeding up Partitions
(using a trick borrowed from Stan Wagon). The helper function h avoids
the use of Prepend.
Attributes[h] = {Listable}
p[n_Integer, b_Integer] := {} /; n < 0
p[n_Integer, b_Integer] := {h[n]} /; n < 2*b
p[n_Integer, b_Integer] := Join[h[b, p[n - b, b]], p[n, b + 1]]
p[0] = {{}}
p[n_Integer] := Apply[List, Flatten /@ p[n, 1], {1}]
The list of unordered partitions is given in lexicographic order instead
of reverse lexicographic order.
Now use p[n] in place of Partitions[n]:
Flatten[Permutations /@ p[n], 1]
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/