Re: Re: [Q] Generalized Partitions
- To: mathgroup at smc.vnet.net
- Subject: [mg30047] Re: [mg29993] Re: [mg29942] [Q] Generalized Partitions
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Wed, 25 Jul 2001 01:00:30 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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/