python - 多项式系数的 Scipy 计算

Question

简短版:标题说明了一切。

日志版本:

我正在为中的前几个元素计算多项式系数。查看 wiki ，数学相当简单。

N! / (k1! * k2! * ....)

对于中等大小的 N，如果你只是暴力破解，数字很快就会变得相当愚蠢。例如，

500!/ (495! * 4! * 1!)

有 500 个!在其中，当表达式也减少时 math.log(factorial(500), 10) ~= 1134:

500!/ (495! * 4! * 1!) = 500 * 499 * 498 * 497 * 496 / 24

我试着玩 scipy.misc.comb ，这对二项式非常有用。对于我的用例，k1 比 ki (i != 1) 大得多，因此我可以计算二项式系数，然后将其转换为相应的多项式系数，但这似乎有点绕。

我认为有更好的方法。

Answer 1

这在数学堆栈交换上得到了回答，看起来很合理。

我认为原来的答案只是枚举所有项并取消，然后计算最终结果。所以从蛮力中删除了 1 步，但看起来它并没有溢出。

也许这与计算生物系数是一样的。反正里面也引用了一个对数算法，我一看没看懂。

https://math.stackexchange.com/questions/204085/how-do-i-compute-multinomials-efficiently