Skip to content

Instantly share code, notes, and snippets.

@dnene
Created March 21, 2012 05:26
Show Gist options
  • Save dnene/2144763 to your computer and use it in GitHub Desktop.
Save dnene/2144763 to your computer and use it in GitHub Desktop.
Polynomial library
# 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment