Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2001
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2001

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

Search the Archive

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



  • Prev by Date: Re: Element-by-element Matrix Multiplication
  • Next by Date: Re: Algorithm
  • Previous by thread: Re: Re: [Q] Generalized Partitions
  • Next by thread: converting old notebooks?