From: Thomas Hafner <thomas@...>
Date: 2007-01-24T20:45:06+09:00
Subject: Re: I need a more efficient algorithm for this problem.

"Sam Kong" <sam.s.kong@gmail.com> wrote/schrieb <1169581542.741753.78250@13g2000cwe.googlegroups.com>:

> Yes. That's much better than the code I posted.

Unfortunately my ``solution'' of
<dfvh84-viu.ln1@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.

Regards
  Thomas