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



On Jan 24, 3:45 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:
> "Sam Kong" <sam.s.k...@gmail.com> wrote/schrieb <1169581542.741753.78...@13g2000cwe.googlegroups.com>:
>
> > Yes. That's much better than the code I posted.Unfortunately my ``solution'' of
> <dfvh84-viu....@faun.hafner.nl.eu.org> is none, because it does not
> report all combinations, sorry. Here's a better approach:
>
> #\\\
> $cache = {}
>
> def parts(s,u)
>   u0 = [s,u].min
>   if u0 < 1
>     []
>   else
>     i = (s-1)*s/2+u0-1
>     $cache[i] ||
>     begin
>       a = []
>       u0.downto(1) do |n|
>         r = s - n
>         if (r > 0)
>           parts(r,n).each do |elem|
>             a.push([n, elem])
>           end
>         else
>           a.push([n])
>         end
>       end
>       $cache[i] = a
>       a
>     end
>   end
> end
>
> def part(n)
>   parts(n,n).map{|x| x.flatten}
> end
> #///
>
> > Actually I've already tried that.
> > But the problem is that even the cached version is not fast enough for
> > my purpose.On my PC evaluation of parts(45) takes 11.53 seconds without cache,
> and 2.96 seconds with cache. But it's definitely not appropriate for
> calculating parts(1000). But you've already mentioned, that you need
> only the number of combinations, not the combinations itself. Many
> years ago at University I've been told that it's often better to solve
> the problem directly. Solving an arbitrary intermediate problem can
> make things worse or even impossible. Here the intermediate problem is
> ``calculate the list of combinations''. Some others are (numerics):
>
> - Don't calculate the inverse of a matrix. The original problem is
>   probably a linear system of equations. Just solve that.
>
> - Never calculate the characteristic polynomial just to find the
>   roots. Solve the Eigenvalue-problem directly.

Yes, you said it right.
I didn't know that the combination grows that fast.
Now I know what's right approach to the solution.

Thanks.

Sam

> 
> Regards
>   Thomas