MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

RE: Re: Re: Re: Help! How to calculate additive partitions?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg34591] RE: [mg34552] Re: [mg34440] Re: Re: [mg34432] Help! How to calculate additive partitions?
  • From: "DrBob" <majort at cox-internet.com>
  • Date: Wed, 29 May 2002 02:44:49 -0400 (EDT)
  • Reply-to: <drbob at bigfoot.com>
  • Sender: owner-wri-mathgroup at wolfram.com

Rob,

That's ingenious, but confusing!  I still have a lot to learn.

When I timed it with 7 other solutions I've looked at, it took about 6%
more time than the best solution so far... the one I called f4, which
makes maximum use of the built in functions:

Needs["DiscreteMath`Combinatorica`"];
f4[n_Integer?Positive] :=
  Flatten[Permutations /@ Partitions[n], 1]

I had been thinking of this as Bob Hanlon's, but I may be confused by
now.

Bobby

-----Original Message-----
From: Rob Pratt [mailto:rpratt at email.unc.edu] 
To: mathgroup at smc.vnet.net
Subject: [mg34591] [mg34552] Re: [mg34440] Re: Re: [mg34432] Help! How to
calculate additive partitions?

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/






  • Prev by Date: Re: A question about Mathematica
  • Next by Date: Re: A question about Mathematica
  • Previous by thread: Re: Re: Re: Help! How to calculate additive partitions?
  • Next by thread: Re: Help! How to calculate additive partitions?