MathGroup Archive 2002

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

Search the Archive

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







  • Prev by Date: RE: Plotting mulitple lists on one log plot
  • Next by Date: Reversed axis on log-linear plot
  • Previous by thread: RE: Re: Re: Re: Help! How to calculate additive partitions?
  • Next by thread: Re: Re: Re: Help! How to calculate additive partitions?