Polynomial library

polynomial.py

# Copied from http://pastebin.com/Vg9Reb0Z to preserve from accidental deletion

# A library for manipulating polynomials in arbitrarily many
# indeterminates and of arbitrary degree. This library is 13 lines of
# code, excluding whitespace and comments. This isn't the smartest or
# most efficient way to do things, but I thought it was a cool way to
# demonstrate the power of itertools
#
# Monomials are pairs of a coefficient and a list of exponents;
# polynomials are lists of monomials.
#
# Thus x^2 y + 3 y^4 z would be represented as
# [(1, [2, 1, 0]), (3, [0, 4, 1])].
#
# Polynomials are added with simple list concatenation (the plus
# operator). Otherwise, the library supports multiplying, reducing,
# multiplying by a scalar, and substituting elements in an arbitrary
# ring.

from itertools import product, starmap, groupby, ifilter, repeat, imap, count

def mm(l, r):
    """multiply monomials"""
    return (l[0] * r[0], map(lambda x, y: (0 if x is None else x) + (0 if y is None else y), l[1], r[1]))

def m(l, r):
    """multiply polynomials"""
    return list(starmap(mm, product(l, r)))

def r(poly):
    """reduce a polynomimal"""
    key = lambda monom: monom[1]
    return list(ifilter(lambda monom: monom[0] != 0, starmap(lambda k, g: (sum(map(lambda monom: monom[0], g)), k),groupby(sorted(poly, key = key), key))))

def p(poly, power):
    """raise a polynomial to a power"""
    return list(reduce(m, repeat(poly, power)))

def cm(c, poly):
    """multiply a polynomial by a scalar"""
    return list(map(lambda monom: (c * monom[0], monom[1]), poly))

def s(poly, rs, m = lambda x, y: x * y, cm = lambda c, r: c * r, one = 1):
    """substitute values for x_1, ..., x_n"""
    return sum(map(lambda monom: cm(monom[0], reduce(m, map(lambda k, r: reduce(m, repeat(r, k), one), monom[1], rs), one)), poly))