From: Rob Biedenharn <Rob@...>
Date: 2007-01-24T05:06:03+09:00
Subject: Re: I need a more efficient algorithm for this problem.


On Jan 23, 2007, at 2:50 PM, Sam Kong wrote:

> Hi Thomas,
>
> Thomas Hafner wrote:
>> "Sam Kong" <sam.s.kong@gmail.com> wrote/schrieb  
>> <1169528870.482644.83900@11g2000cwr.googlegroups.com>:
>>
>>> Do you know a good solution to this problem?
>>
>> #///
>
> Yes. That's much better than the code I posted.
> Actually I've already tried that.
> But the problem is that even the cached version is not fast enough for
> my purpose.
> James's non-recursive code is not fast enough either.
>
> Probably, the solution to my problem is not just algorithm.
> I need to find a mathematical formula.
>
> See http://home.att.net/~numericana/data/partition.htm
> What I want is not the array of partitions but only the size of
> partitions.
> For example, the number of different ways to make 1000 is
> 24061467864032622473692149727991.
> It's almost impossible to keep an array of that size.
>
> I'm satisfied with this thread of talks because it taught me some even
> if I couldn't find the answer.
>
> Thanks.
>
> Sam

These are Catalan numbers which you can learn more about on Wikipedia 
[1] or MathWorld[2].  If you just need to know the number of  
solutions, both references give a formula.

-Rob

[1] http://en.wikipedia.org/wiki/Catalan_number
[2] http://mathworld.wolfram.com/CatalanNumber.html

Rob Biedenharn		http://agileconsultingllc.com
Rob@AgileConsultingLLC.com