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/