Creating an array that multiplies and adds its elements in all unique possible combinations

user_17828112 0
Viewed 47

I am currently working on a project for calculating polynomial shifts via python of nth degree. The user can input n amount of inputs which get stored in an array that then get converted via the shift and turned back into a new polynomial. The problem is, the higher the degree of n, the more calculations necessary to turn the shifted value to it's polynomial coefficient:

What the program should do is add and multiply all the values uniquely and save the result in a new array:

e.g. for a polynomial of degree 4, it will have inputs [a,b,c,d]

shiftedPCL[0] = a + b + c + d
shiftedPCL[1] = a*b + b*c + c*d + a*c + b*d + a*d
shiftedPCL[2] = a*b*c + b*c*d + a*b*d + a*c*d
shiftedPCL[3] = a*b*c*d

The first and last lines of the equations can be solved simply by summing and multiplying all the values in a list respectively, and I have created a simple recursive code to calculate the second to last line of equations using recursion, but for n greater than 3 it is useless, as it cannot calculate any lines that aren't the first, last or second to last.

This is why I would like to know if there's a way to add and multiply all elements in a list as shown above (for lists of any length).

recursion math arrays python
3 Answers

The easiest way to do this in my opinion would be using python itertool. Python itertool is a module that provides various functions that work on iterators to produce complex iterators. The function is itertools permutations. This might be the easiest though slowest program:

from itertools import permutations
list1 = [1,2,3,4] #replace with a, b, c and d
shiftedPCL = []
for i in range(1,len(list1)+1):
    comb = permutations(list1, i)
    sum1 = 0
    for j in comb:
        print(j)
        result = 1
        for x in j:
            result = result * x
        sum1 += result
    shiftedPCL.append(sum1)

print(shiftedPCL)

Variable Names changed as recommended by @Stef

user_181164170

What you are trying to do is the expansion of a product of monic binomials like

(x+a)(x+b)(x+c)(x+d) = x^4 + Ax^3 + Bx^2 + Cx + D.

Don't do that by means of the (modified) Vieta's formulas. Instead, apply one binomial at a time.

E.g. after three factors already expanded,

(x^3 + Px^2 + Qx + R)(x + d) = x^4 + (P + d) x^3 + (Q + Pd) x^2 + (R + Qd) x + Rd.
user_11965490

The element at index i in your resulting array is the sum of all products of combinations of i elements.

In python, the sum of all products of combinations of i elements from a list l can be written as:

sum(map(prod, combinations(l,i)))

Where sum and map are builtin functions, and prod and combinations are imported from standard library modules math and itertools, respectively.

from itertools import combinations
from math import prod

def sums_of_products(l):
    return [sum(map(prod, combinations(l,i))) for i in range(1, len(l)+1)]

We can test this function with numbers, or with symbols using sympy:

from sympy import symbols

a,b,c,d = symbols('a b c d')
print( sums_of_products([a,b,c,d]) )
# [a + b + c + d,
#  a*b + a*c + a*d + b*c + b*d + c*d,
#  a*b*c + a*b*d + a*c*d + b*c*d,
#  a*b*c*d]

print( sums_of_products([2,3,5,7]) )
# [17, 101, 247, 210]
user_30807230
Related