Adding polynomial equations using dictionaries in Python

Question

I'm trying to add two polynomial equations which are in list structure such as below:

[(2,3),(6,2),(-2, 1)], [(-4,3),(2,2),(2,1)]

Which means:

(2x³ + 6x² - 2x) + (-4x³ + 2x² + 2x)

I came up with below script to first convert them to dictionary and add the keys.

def combine(p1, p2):
    total = {}
    d1 = dict(p1)
    d2 = dict(p2)
    print('The dictionaries are: ', d1, d2)
    for e in d1.keys():
        for p in d2.keys():
            if d1[e] == d2[p]:#add only if the exponential match
                total[e + p] = d2[p]
                print(total)

This works fine for some value and provide incorrect results for some other values. I'm not entirely sure what is wrong with the above script.

Example 1: (working fine)
>>> combine([(4,3),(3,2),(10, 1)], [(-4,3),(2,2),(8,1)])
The dictionaries are:  {4: 3, 3: 2, 10: 1} {-4: 3, 2: 2, 8: 1}
{0: 3}
{0: 3, 5: 2}
{0: 3, 5: 2, 18: 1}

Example 2: (Incorrect Result)
>>> combine([(4,3),(3,2),(10, 1)], [(-4,3),(2,2),(-10,1)])
The dictionaries are:  {4: 3, 3: 2, 10: 1} {-4: 3, 2: 2, -10: 1}
{0: 3}
{0: 3, 5: 2}
{0: 1, 5: 2}

Example 3: (Incorrect Result)
>>> combine([(2,3),(6,2),(-2, 1)], [(-4,3),(2,2),(2,1)])
The dictionaries are:  {2: 3, 6: 2, -2: 1} {-4: 3, 2: 1}
{-2: 3}
{-2: 3, 0: 1}

Can you please let me know to identify the issues in the above script?

Answer 1

Using one dictionary with the exponents as keys and coefficients as values:

from collections import defaultdict

def combine(p1, p2):
    total = defaultdict(int)
    for coefficient, exponent in p1 + p2:
        total[exponent] += coefficient
    return [item[::-1] for item in total.items()]

p1, p2 = [(2,3),(6,2),(-2, 1)], [(-4,3),(2,2),(2,1)]
print(combine(p1, p2))

Output:

[(-2, 3), (8, 2), (0, 1)]

If you represented the terms not as (coefficient, exponent) but as (exponent, coefficient) then you could just end with this:

    return list(total.items())

Then again, list comprehension makes it easy to filter zeros if you want (you didn't say):

    return [(coefficient, exponent)
            for exponent, coefficient in total.items()
            if coefficient]

Answer 2

The problem is that when multiple terms have the same coefficient after being added, they will have the same key. This means that the values will be overwritten as the iteration continues.

My solution would to actually make the exponent as the key and the coefficient as the value since the exponents will be unique:

def switch(p1):
  newP = []
  for index, tuple in enumerate(p1):
    newP.append((tuple[1],tuple[0]))
  return newP

This function takes in a list of tuples as its parameter, and switches the order. Thus, when we convert them to dictionaries, the keys and values will switch, allowing the keys to be exponents:

def combine(p1, p2):
    total = {}
    p1 = switch(p1)
    p2 = switch(p2)
    d1 = dict(p1)
    d2 = dict(p2)
    print('The dictionaries are: ', d1, d2)
    for e in d1.keys():
        for p in d2.keys():
            if e == p:#add only if the exponential match
                total[e] = d1[e] + d2[p]
                print(printPoly(total))

I created a function, printPoly() to make the printing more readable:

def printPoly(total):
    output = ""
    for key, value in total.items():
         output += str(value) + "x^" + str(key) + "+"
    return output[0:-1]

Now lets test our final code:

def switch(p1):
  newP = []
  for index, tuple in enumerate(p1):
    newP.append((tuple[1],tuple[0]))
  return newP
  
def combine(p1, p2):
    total = {}
    p1 = switch(p1)
    p2 = switch(p2)
    d1 = dict(p1)
    d2 = dict(p2)
    print('The dictionaries are: ', d1, d2)
    for e in d1.keys():
        for p in d2.keys():
            if e == p:#add only if the exponential match
                total[e] = d1[e] + d2[p]
                print(printPoly(total))

def printPoly(total):
    output = ""
    for key, value in total.items():
         output += str(value) + "x^" + str(key) + "+"
    return output[0:-1]

Test: combine([(4,3),(3,2),(10, 1)], [(-4,3),(2,2),(8,1)])

Output: 0x^3+5x^2+18x^1

Test: combine([(4,3),(3,2),(10, 1)], [(-4,3),(2,2),(-10,1)])

Output: 0x^3+5x^2+0x^1

Test: combine([(2,3),(6,2),(-2, 1)], [(-4,3),(2,2),(2,1)])

Output: -2x^3+8x^2+0x^1

NOTE: If you do not want to use the printPoly() function to get it in a polynomial form, you can simply change:

print(printPoly(total))

to:

print(total)

though simply printing total will list exponents first, and then the coefficient.

I hope this helped! Please let me know if you need any further clarification or details :)

(I really enjoyed this problem)

Answer 3

Let's define data.

data = [[(2,3),(6,2),(-2, 1)], [(-4,3),(2,2),(2,1)]]

Now, let's write a generator expression to flatten that.

(y for x in data for y in x)

And import itertools.groupby.

from itertools import groupby

Next we'll define a couple of utility functions to extract element from two element tuples.

def fst(tpl): return tpl[0]
def snd(tpl): return tpl[1]

Now we can sort the flattened data by the exponent value, in descending order.

sorted((y for x in data for y in x), key=snd, reverse=True)

This gives us:

[(2, 3), (-4, 3), (6, 2), (2, 2), (-2, 1), (2, 1)]

And using groupby:

groupby(sorted((y for x in data for y in x), key=snd, reverse=True), key=snd)

Exponents are the keys here, and the coefficient/exponent tuples matching them are the values.

Now we just need a list comprehension in which we'll use map to extract all of the coefficients and sum to add them.

[(sum(map(fst, c)), e) for e, c in groupby(sorted((y for x in data for y in x), key=snd, reverse=True), key=snd)]

End result?

[(-2, 3), (8, 2), (0, 1)]