Re: Re: Re: [Q] Generalized Partitions
- To: mathgroup at smc.vnet.net
- Subject: [mg30082] Re: [mg30047] Re: [mg29993] Re: [mg29942] [Q] Generalized Partitions
- From: andrzej <andrzej at bekkoame.ne.jp>
- Date: Fri, 27 Jul 2001 03:52:19 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Michael Trott has pointed out that the code for kpartitions I sent was
very wasteful. He provided the correct version, which is:
kpartitions[n_, k_, l_List] :=
SeriesCoefficient[Series[SeriesCoefficient[
Series[Times @@ ((1/(1 - t*x^#)) & /@ l), {x, 0, n}], n], {t, 0,
k}], k]
This avoids computing unneeded terms and is very much faster than my
original version. In fact it is now the second fastest method I know,
and in the case I considered earlier gives:
In[26]:=
kpartitions[51,6,L]//Timing
Out[26]=
{0.66 Second,109}
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
On Wednesday, July 25, 2001, at 02:00 PM, Andrzej Kozlowski wrote:
> 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/
>
>
>
>
>