Multiply multivariate polynomials

Question

We already have a challenge about multiplying multiply single-variable polynomials. This challenge is about multiply two polynomials with multiple variables

Your task is given two multi-variable polynomials (for instance given as nested lists) to return their product.

Examples

(x²+x+1)*(x²+x+1)=x⁴+2x³+3x²+2x+1
(x+y)*(x+y)=x²+2xy+y²
(x+y+z)*(x-y+z) = x²-y²+2xz +z²
a*a=a²

when representing polynomials as nested lists¹:

[1,1,1], [1,1,1]                                     -> [1, 2, 3, 2, 1]
[[0,1],[1]], [[0,1],[1]]                             -> [[0, 0, 1], [0, 2], [1]]
[[[0,1],[1]],[[1]]], [[[0,1],[-1]],[[1]]]            -> [[[0, 0, 1], [0], [-1]], [[0, 2]], [[1]]]
[[],[[[[[[[[[1]]]]]]]]]], [[],[[[[[[[[[1]]]]]]]]]] -> [[], [], [[[[[[[[[1]]]]]]]]]]

(non-golfed) solution in Python

Rules

• You can Input/Output the polynomials in any convenient format (as long as each output can only represent one polynomial)
• Input and Output have to use the same format for polynomials
• You can assume that all coefficients are integers
• If you take input as lists you can assume that all numbers in both inputs appear in the nesting depth
• You are allowed to omit zero coefficients in the output (as long as the output value are unambiguous)
• You can use the empty list to represent zero/the zero polynomial
• If your language has a built-in for multi-variable polynomial multiplication consider adding a non-built-in solution as well
• This is code-golf the shortest solution wins

---

¹short explanation of the nested list format used in the examples (you are free to use a different IO format):

Each list represents a single variable polynomial with its coefficients begin either integers or other lists representing polynomials in one less variable. The coefficients are multiplied with the polynomial variable to the power of their index:

[[[0,1],[1]],[[1]]] -> "[[0,1],[1]]"*1+"[[1]]"*z -> ("[0,1]"*1+"[1]"*y)*1+"[1]"*1*z -> (x*1+1*y)*1+1*1*z -> x+y+z

The variables are assigned by nesting layer. I use x for the innermost variable y for the next level, then z.

Answer 1

JavaScript (Node.js), 80 bytes

f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i++]||=[])||(s[i-1]-=-p*q)))&&s

Attempt This Online!

JavaScript (Node.js), 84 bytes

f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i]=s[i++]||[])||(s[i-1]-=-p*q)))&&s

Try it online!

Answer 2

Charcoal, 115 112 bytes

ＦＥθ⟦⟦ι⟧⟧«Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι⊞υι»≔⟦⟧θＦ⊟υ«≔⊟ιηＦ⌊υ«≔Ｅι⁺λ§κμζ≔⊟ζε≔θδＦζ≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδＦ⁼εＬδ⊞δ⁰§≔δε⁺§δε×↨κ⁰η»»⭆¹θ

Attempt This Online! Link is to verbose version of code. Explanation: Charcoal doesn't really like multidimensional indexing. I should really find time to test this out on my multidimensional indexing branch to see whether it offers a significant saving.

ＦＥθ⟦⟦ι⟧⟧«

Double wrap each input polynomial and then loop over them.

Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι

Replace each polynomial with a list of its elements and their multidimensional indices.

⊞υι

Save the resulting list.

»≔⟦⟧θ

Start building up the output list.

Ｆ⊟υ«

Loop over the second polynomial's multidimensional index list.

≔⊟ιη

Remove the coefficient from the multidimensional index.

Ｆ⌊υ«

Loop over the first polynomial's multidimensional index list.

≔Ｅι⁺λ§κμζ

Get the multidimensional index of the product of the two terms.

≔⊟ζε

Remove the innermost index.

≔θδ

Start traversing the dimensions of the output list.

Ｆζ

Loop over the earlier multidimensional indices.

≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδ

Get the inner list at the current multidimensional index, extending the current list if necessary.

Ｆ⁼εＬδ⊞δ⁰

Extend the innermost list if necessary.

§≔δε⁺§δε×↨κ⁰η

Add on the resulting coefficient to the element at the innermost index.

»»⭆¹θ

Pretty-print the resulting list.

Answer 3

K (ngn/k), ⁶⁰ 55 bytes

{(.p),','!p:+/'(*p)@=*|p:(*/;+/)@''++',/,/:\:/,''(x;y)}

Try it online!

-5 : Save a lambda

Here multinomials are represented by lists of terms where each term is a pair of coefficients and list of powers of each variable in reverse order.

Thus,

(x-y+z) -> [[[1,[0,0,1]],[-1,[0,1,0]],[1,[0,0,1]]]

or in K notation:

((1;0 0 1)
 (-1;0 1 0)
 (1;1 0 0))

Cleaning up terms with zero coefficients is left to an auxiliary function.

Answer 4

Python3, 490 bytes:

def U(p,l=1,o=1):
 if type(p)!=list or[]==p:yield(p if p!=[]else 0,o);return
 for i,a in enumerate(p):yield from U(a,l+1,{l:i}if o==1 else{**o,l:o.get(l,0)+i})
def G(p,l=1):
 r={}
 for c,D in p:
  if l in D:r[V]=r.get(V:=D.pop(l),[])+[(c,D)]
 return[G(r[i],l+1)if i in r else 0 for i in range(max(r)+1)]if r else c
def M(a,b):
 r={}
 for c,p in U(a):
  for C,P in U(b):r[K]=r.get(K:=str({**p,**{A:p.get(A,0)+B for A,B in P.items()}}),0)+c*C
 return G([(b,eval(a))for a,b in r.items() if b])

Try it online!

Answer 5

Wolfram Language (Mathematica), 12 bytes

Expand[1##]&

Try it online. The inevitable built-in. 1## multiplies together all arguments to a function, regardless of the types of those objects. (So this function works for more than two polynomials as well.)