From: Sam Kong <sam.s.kong@...>
Date: 2007-01-24T04:50:09+09:00
Subject: Re: I need a more efficient algorithm for this problem.

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?
>
> I let you decide if mine is a good solution:
>
> #\\\
> $cache = []
>
> def parts(s)
>   if s < 1
>     []
>   else
>     $cache[s] ||
>     begin
>       a = []
>       s.downto(1) do |n|
>         k = s / n
>         left = [].fill(n, (0 .. (k-1)))
>         r = s - k * n
>         if (r > 0)
>           right = parts(r)
>           right.each do |elem|
>               a.push([left,elem])
>           end
>         else
>           a.push(left)
>         end
>       end
>       $cache[s] = a
>     end
>   end
> end
>
> def part(n)
>   parts(n).map{|x| x.flatten}
> end
>
> pp part(8)
> #///

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