RE: Re: Help! How to calculate additive partitions?
- To: mathgroup at smc.vnet.net
- Subject: [mg34468] RE: [mg34441] Re: [mg34432] Help! How to calculate additive partitions?
- From: "DrBob" <majort at cox-internet.com>
- Date: Thu, 23 May 2002 03:32:07 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
Here's timing for Fred Simons' method, for n=20:
ClearAll[f]
f[0] = {{}};
f[n_Integer] :=
Flatten[Table[{k, ##} & @@@ f[n - k], {k, 1, n}], 1]
First[Timing[f[20];]]
31.656 Second
To get more understanding of what's going on, let's count the number of
times f is invoked for each n:
ClearAll[c, f]
c[n_Integer] := 0
f[0] := (c[0]++; {{}})
f[n_Integer] := (
c[n]++;
Flatten[Table[{k, ##} & @@@ f[n - k], {k, 1, n}], 1]
)
First[Timing[f[20];]]
c /@ Range[0, 20]
43.687 Second
{524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024,
512,
256, 128, 64, 32, 16, 8, 4, 2, 1, 1}
This seems wasteful since, for instance, all 131,072 times f[2] was
computed, the answer was the same! So... the usual (dynamic
programming) method to speed up recursion is to save and reuse answers.
Here's a routine that computes partitions of "target" while saving f[n]
(using Set) whenever n <= lim, and returns timing only.
g[n_Integer] := Flatten[Table[{k, ##} & @@@ f[n - k], {k, 1, n}], 1];
setUntil[target_Integer, lim_Integer] := (
ClearAll[f];
f[0] = {{}};
f[n_Integer] /; n <= lim := f[n] = g[n];
f[n_Integer] : = g[n];
First[Timing[f[target];]] /. Second \[Rule] 1
)
Next we try it for target=20 and values of "lim" from 1 to 20. (Don't
try this without a fast Pentium 4. Lots of memory comes in handy too.)
setUntil[20, #] & /@ Range[20]
Plus @@ %
{29.266, 24.516, 21.109, 18.672, 17.343, 16.281, 15.156, 14.203, 13.188,
12.484, 11.703, 10.797, 9.719, 8.563, 7.75, 6.437, 5.406, 4.781, 4.984,
4.625}
256.983
There's a diminishing return on investment as "lim" increases because
(as seen earlier) the invocation counts go down rapidly.
Memory requirements (for intermediate answers) double at each step, but
half the total memory required is used by the final answer anyway. THAT
memory requirement can't be avoided --- unless we arrange to Print
partitions as we go, rather than assembling them for display together.
Here's a look at how timing changes with n, using lim=n in each case:
setUntil[#, #] & /@ Range[22]
Plus @@ %
{0., 0., 0., 0., 0., 0., 0., 0., 0.015, 0., 0., 0.016, 0.031, 0.063,
0.14, \
0.281, 0.563, 1.125, 2.313, 4.64, 8.61, 16.25}
34.047
Bobby Treat
-----Original Message-----
From: Fred Simons [mailto:f.h.simons at tue.nl]
To: mathgroup at smc.vnet.net
Subject: [mg34468] [mg34441] Re: [mg34432] Help! How to calculate additive
partitions?
Tom,
Let n be a positive integer and let f[n] be the list of all additive
partitions of n. The partitions starting with 1 have the additive
partitions
of n-1 as rest, those starting with 2 are followed by the additive
partitions of n-2 and so on. From this observation we conclude that the
length of f[n] equals 2^(n-1). So to construct all partitions is only
feasible for small values of n. We then can use the following recursive
implementation of the idea above:
f[0]={{}};
f[n_Integer] := Flatten[Table[{k, ##}& @@@ f[n-k], {k, 1, n}], 1]
In[117]:= f[4]
Out[117]=
{{1,1,1,1},{1,1,2},{1,2,1},{1,3},{2,1,1},{2,2},{3,1},{4}}
Indeed we have 2^(4-1) partitions.
Fred Simons
Eindhoven University of Technology