Stirling Numbers In Ruby

From: http://www.ruby-forum.com/topic/95068
Author: Thomas Hafner

http://en.wikipedia.org/wiki/Stirling_number 
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind




$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

p part(5)     #=> [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]