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/ > > > > >