Después de indagar en diversos repositorios y sitios webs al final hemos descubierto la solución que te enseñaremos a continuación.
Solución:
Para responder parcialmente a mi propia pregunta, aquí está mi implementación simple y bastante eficiente de la función multinomial:
def multinomial(lst):
res, i = 1, 1
for a in lst:
for j in range(1,a+1):
res *= i
res //= j
i += 1
return res
Parece por los comentarios hasta ahora que no existe una implementación eficiente de la función en ninguna de las bibliotecas estándar.
Actualización (enero de 2020). Como ha señalado Don Hatch en los comentarios, esto se puede mejorar aún más buscando el argumento más grande (especialmente en el caso de que domine a todos los demás):
def multinomial(lst):
res, i = 1, sum(lst)
i0 = lst.index(max(lst))
for a in lst[:i0] + lst[i0+1:]:
for j in range(1,a+1):
res *= i
res //= j
i -= 1
return res
No, no hay una biblioteca o función multinomial incorporada en Python.
De todos modos, esta vez las matemáticas podrían ayudarte. De hecho, un método simple para calcular el multinomio
vigilar el rendimiento es reescribirlo utilizando la caracterización del coeficiente multinomial como producto de coeficientes binomiales:
donde por supuesto
Gracias a scipy.special.binom y la magia de la recursividad puedes resolver el problema así:
from scipy.special import binom
def multinomial(params):
if len(params) == 1:
return 1
return binom(sum(params), params[-1]) * multinomial(params[:-1])
donde params = [n1, n2, ..., nk].
Nota: Dividir el multinomio como producto del binomio también es bueno para evitar el desbordamiento en general.
Tu escribiste “sympy.ntheory.multinomial.multinomial_coefficients devuelve un diccionario relacionado con coeficientes multinomiales”, pero no queda claro a partir de ese comentario si sabe cómo extraer los coeficientes específicos de ese diccionario. Usando la notación del enlace de wikipedia, la función SymPy te da todo los coeficientes multinomiales para el dado metro y norte. Si solo desea un coeficiente específico, simplemente sáquelo del diccionario:
In [39]: from sympy import ntheory
In [40]: def sympy_multinomial(params):
...: m = len(params)
...: n = sum(params)
...: return ntheory.multinomial_coefficients(m, n)[tuple(params)]
...:
In [41]: sympy_multinomial([1, 2, 3])
Out[41]: 60
In [42]: sympy_multinomial([10, 20, 30])
Out[42]: 3553261127084984957001360
Busy Beaver dio una respuesta escrita en términos de scipy.special.binom. Un problema potencial con esa implementación es que binom(n, k) devuelve un valor de punto flotante. Si el coeficiente es lo suficientemente grande, no será exacto, por lo que probablemente no te ayude con un problema del Proyecto Euler. En vez de binom, puedes usar scipy.special.comb, con el argumento exact=True. Esta es la función de Busy Beaver, modificada para usar comb:
In [46]: from scipy.special import comb
In [47]: def scipy_multinomial(params):
...: if len(params) == 1:
...: return 1
...: coeff = (comb(sum(params), params[-1], exact=True) *
...: scipy_multinomial(params[:-1]))
...: return coeff
...:
In [48]: scipy_multinomial([1, 2, 3])
Out[48]: 60
In [49]: scipy_multinomial([10, 20, 30])
Out[49]: 3553261127084984957001360
Aquí puedes ver las reseñas y valoraciones de los usuarios
Si te ha sido de ayuda nuestro artículo, agradeceríamos que lo compartas con el resto entusiastas de la programación de este modo contrubuyes a difundir nuestra información.