Stirling Numbers In Ruby
Join the DZone community and get the full member experience.
Join For Free
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]]
Opinions expressed by DZone contributors are their own.
Comments