Expresando cantidades de productos en términos de sumas de potencias

Question

Estoy trabajando en la construcción de algún tipo de software que hace la máquina de aprendizaje. Uno de los problemas a los que me he topado es que, tengo un array de números:

$[{a, b, c, d}]$

Y quiero calcular de la siguiente manera eficiente:

$ab + ac + ad + bc + bd + cd$

O:

$abc + abd + acd + bcd$

Donde el número de variables en cada grupo se especifica de forma arbitraria. Tengo un método en el que yo uso:

$f(x) = a^x + b^x + c^x + d^x$

Y, a continuación, calcular:

$f(1) = a + b + c + d$

$(f(1)^2-f(2))/2 = ab + ac + ad + bc + bd + cd$

$(f(1)^3 - 3f(2)f(1) + 2f(3))/6 = abc + abd + acd + bcd$

$(f(1)^4 - 6f(2)f(1)^2 + 3f(2)^2 + 8f(3)f(1) - 6f(4))/24 = abcd$

Pero he trabajado estos de forma manual y estoy luchando para generalizar. La matriz será normalmente mucho más y me voy a querer para calcular mucho órdenes superiores.

Answer 1

Ver identidades en.wikipedia.org/wiki/Newton's_identities de Newton

Answer 2

Además de utilizar el método de Newton identidades como se mencionó en @Soarer comentario, usted también podría considerar la posibilidad de un algoritmo para generar todas las combinaciones. E. g. para calcular $$abc+abd+acd+bcd$$ se generaría 3-combinaciones de 4 elementos. Quedarse con este ejemplo, usted ya tiene una matriz de números $a = [a_0, a_1, a_2, a_3]$ por lo que se podría generar todas las posibles ternas de los índices de $(i, j, k), i < j < k$ y, a continuación, multiplica y suma $a_i * a_j * a_k$. Este método podría ser numéricamente más robusto, a continuación, Newton identidades porque sólo adiciones y no restas, divisiones se utilizan. La eficiencia también podría ser favorable, pero esto requeriría un mayor análisis. Hay tal vez aún más eficiente algoritms.