MathGroup Archive 2001

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

Search the Archive

Re: Re: [Q] Generalized Partitions


While thinking of Janusz Kawczak's partition problem I found the following
amusing way to compute the number of partitions of an integer n as a sum
of k-elements of a given list l.

kpartitions[n_, k_, l_List] := Coefficient[ Normal[Series[Times @@ ((1/(1 -
t*x^#)) & /@ l), {x, 0, n}, {t, 0, k}]], x^n t^k]

I leave the proof that this is correct as an exercise for the reader :)
For example:

for n=51, k=6 and 
L={1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,47,50,53,56,59};

In[24]:=
kpartitions[51,6,L]//Timing
Out[24]=
{3.58 Second,109}

Unfortunately this is rather slow since on the same computer my Backtrack
method gives:

In[28]:=
Length[sols=Backtrack[sp,partialQ,solutionQ,All]]//Timing
Out[28]=
{1.01 Second,109}

and the even faster iterative approach of Daniel Lichtblau gives:

In[32]:=
Length[gPartitions[L,51,6]]//Timing
Out[32]=
{0.32 Second,109}

Sadly the solutions that seem mathematically most satisfying are not always
the most efficient :(


-- 
Andrzej Kozlowski
Toyama International University
JAPAN

http://platon.c.u-tokyo.ac.jp/andrzej/




  • Prev by Date: RE: Re: Folds
  • Next by Date: Re: Filename as Function Argument
  • Previous by thread: Re: [Q] Generalized Partitions
  • Next by thread: Re: Re: Re: [Q] Generalized Partitions