On Mon, Apr 23, 2007 at 06:25:39PM -0500, Dan Drake wrote:
I'm finding the number of set partitions that correspond to a certain integer partition. If p = p_1, p_2,...,p_k is an integer partition of n, then there are
n! ---------------------------------------------- p_1! * p_2! * ... * p_k! * 1^c_1 * ... * k^c_k ... Doing cancellation before computing the factorials is also an option, but in general I'll have a lot of small numbers on the bottom, and would need to do a lot of integer factoring on the top -- and my impression is that integer factoring is quite slow, faster than integer multiplication -- that's why RSA works, right?!
In many cases, cancelling out the largest factorial on the bottom should be a win: n! x = ------------------------ p_1! * p_2! * ... * p_k! x n ps = product [max ps..n] / (product $ concat $ map (\p->[1..p]) $ delete (max ps) ps) and yes, that's pseudocode... max has wrong type. of course, this only helps if you've got a big p. At least there's always a biggest p. -- David Roundy Department of Physics Oregon State University