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

"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)
#///

Regards
  Thomas