# Source code for sympy.polys.monomialtools

"""Tools and arithmetics for monomials of distributed polynomials. """

from sympy.core.mul import Mul
from sympy.core.singleton import S
from sympy.core.basic import C

from sympy.polys.polyerrors import ExactQuotientFailed

from sympy.utilities import cythonized

from sympy.core.compatibility import cmp

[docs]def monomials(variables, degree):
r"""
Generate a set of monomials of the given total degree or less.

Given a set of variables V and a total degree N generate
a set of monomials of degree at most N. The total number of
monomials is huge and is given by the following formula:

.. math::

\frac{(\#V + N)!}{\#V! N!}

For example if we would like to generate a dense polynomial of
a total degree N = 50 in 5 variables, assuming that exponents
and all of coefficients are 32-bit long and stored in an array we
would need almost 80 GiB of memory! Fortunately most polynomials,
that we will encounter, are sparse.

**Examples**

Consider monomials in variables x and y::

>>> from sympy import monomials
>>> from sympy.abc import x, y

>>> sorted(monomials([x, y], 2))
[1, x, y, x**2, y**2, x*y]

>>> sorted(monomials([x, y], 3))
[1, x, y, x**2, x**3, y**2, y**3, x*y, x*y**2, x**2*y]

"""
if not variables:
return set([S.One])
else:
x, tail = variables[0], variables[1:]

monoms = monomials(tail, degree)

for i in range(1, degree+1):
monoms |= set([ x**i * m for m in monomials(tail, degree-i) ])

return monoms

[docs]def monomial_count(V, N):
r"""
Computes the number of monomials.

The number of monomials is given by the following formula:

.. math::

\frac{(\#V + N)!}{\#V! N!}

where N is a total degree and V is a set of variables.

**Examples**

>>> from sympy import monomials, monomial_count
>>> from sympy.abc import x, y

>>> monomial_count(2, 2)
6

>>> M = monomials([x, y], 2)

>>> sorted(M)
[1, x, y, x**2, y**2, x*y]
>>> len(M)
6

"""
return C.factorial(V + N) / C.factorial(V) / C.factorial(N)

def monomial_lex_key(monom):
"""Key function for sorting monomials in lexicographic order. """
return monom

def monomial_grlex_key(monom):
"""Key function for sorting monomials in graded lexicographic order. """
return (sum(monom), monom)

def monomial_grevlex_key(monom):
"""Key function for sorting monomials in reversed graded lexicographic order. """
return (sum(monom), tuple(reversed(monom)))

_monomial_key = {
'lex'     : monomial_lex_key,
'grlex'   : monomial_grlex_key,
'grevlex' : monomial_grevlex_key,
}

def monomial_key(order=None):
"""
Return a function defining admissible order on monomials.

The result of a call to :func:monomial_key is a function which should
be used as a key to :func:sorted built-in function, to provide order
in a set of monomials of the same length.

Currently supported monomial orderings are:

1. lex       - lexicographic order (default)
2. grlex     - graded lexicographic order
3. grevlex   - reversed graded lexicographic order

If the input argument is not a string but has __call__ attribute,
then it will pass through with an assumption that the callable object
defines an admissible order on monomials.

"""
if order is None:
return _monomial_key['lex']

if isinstance(order, str):
try:
return _monomial_key[order]
except KeyError:
raise ValueError("supported monomial orderings are 'lex', 'grlex' and 'grevlex', got %r" % order)
elif hasattr(order, '__call__'):
return order
else:
raise ValueError("monomial ordering specification must be a string or a callable, got %s" % order)

def monomial_lex_cmp(a, b):
return cmp(a, b)

def monomial_grlex_cmp(a, b):
return cmp(sum(a), sum(b)) or cmp(a, b)

def monomial_grevlex_cmp(a, b):
return cmp(sum(a), sum(b)) or cmp(tuple(reversed(b)), tuple(reversed(a)))

_monomial_order = {
'lex'     : monomial_lex_cmp,
'grlex'   : monomial_grlex_cmp,
'grevlex' : monomial_grevlex_cmp,
}

def monomial_cmp(order):
"""
Returns a function defining admissible order on monomials.

Currently supported orderings are:

1. lex       - lexicographic order
2. grlex     - graded lexicographic order
3. grevlex   - reversed graded lexicographic order

"""
try:
return _monomial_order[order]
except KeyError:
raise ValueError("expected valid monomial order, got %s" % order)

@cythonized("a,b")
def monomial_mul(A, B):
"""
Multiplication of tuples representing monomials.

Lets multiply x**3*y**4*z with x*y**2::

>>> from sympy.polys.monomialtools import monomial_mul

>>> monomial_mul((3, 4, 1), (1, 2, 0))
(4, 6, 1)

which gives x**4*y**5*z.

"""
return tuple([ a + b for a, b in zip(A, B) ])

@cythonized("a,b,c")
def monomial_div(A, B):
"""
Division of tuples representing monomials.

Lets divide x**3*y**4*z by x*y**2::

>>> from sympy.polys.monomialtools import monomial_div

>>> monomial_div((3, 4, 1), (1, 2, 0))
(2, 2, 1)

which gives x**2*y**2*z. However::

>>> monomial_div((3, 4, 1), (1, 2, 2)) is None
True

x*y**2*z**2 does not divide x**3*y**4*z.

"""
C = [ a - b for a, b in zip(A, B) ]

if all([ c >= 0 for c in C ]):
return tuple(C)
else:
return None

@cythonized("a,b")
def monomial_gcd(A, B):
"""
Greatest common divisor of tuples representing monomials.

Lets compute GCD of x**3*y**4*z and x*y**2::

>>> from sympy.polys.monomialtools import monomial_gcd

>>> monomial_gcd((3, 4, 1), (1, 2, 0))
(1, 2, 0)

which gives x*y**2.

"""
return tuple([ min(a, b) for a, b in zip(A, B) ])

@cythonized("a,b")
def monomial_lcm(A, B):
"""
Least common multiple of tuples representing monomials.

Lets compute LCM of x**3*y**4*z and x*y**2::

>>> from sympy.polys.monomialtools import monomial_lcm

>>> monomial_lcm((3, 4, 1), (1, 2, 0))
(3, 4, 1)

which gives x**3*y**4*z.

"""
return tuple([ max(a, b) for a, b in zip(A, B) ])

@cythonized("i,n")
def monomial_max(*monoms):
"""
Returns maximal degree for each variable in a set of monomials.

Consider monomials x**3*y**4*z**5, y**5*z and x**6*y**3*z**9.
We wish to find out what is the maximal degree for each of x, y
and z variables::

>>> from sympy.polys.monomialtools import monomial_max

>>> monomial_max((3,4,5), (0,5,1), (6,3,9))
(6, 5, 9)

"""
M = list(monoms[0])

for N in monoms[1:]:
for i, n in enumerate(N):
M[i] = max(M[i], n)

return tuple(M)

@cythonized("i,n")
def monomial_min(*monoms):
"""
Returns minimal degree for each variable in a set of monomials.

Consider monomials x**3*y**4*z**5, y**5*z and x**6*y**3*z**9.
We wish to find out what is the minimal degree for each of x, y
and z variables::

>>> from sympy.polys.monomialtools import monomial_min

>>> monomial_min((3,4,5), (0,5,1), (6,3,9))
(0, 3, 1)

"""
M = list(monoms[0])

for N in monoms[1:]:
for i, n in enumerate(N):
M[i] = min(M[i], n)

return tuple(M)

[docs]class Monomial(object):
"""Class representing a monomial, i.e. a product of powers. """

__slots__ = ['data']

def __init__(self, *data):
self.data = tuple(map(int, data))

def __hash__(self):
return hash((self.__class__.__name__, self.data))

def __repr__(self):
return "Monomial(%s)" % ", ".join(map(str, self.data))

def as_expr(self, *gens):
"""Convert a monomial instance to a SymPy expression. """
return Mul(*[ gen**exp for gen, exp in zip(gens, self.data) ])

def __eq__(self, other):
if isinstance(other, Monomial):
return self.data == other.data
else:
return False

def __ne__(self, other):
return not self.__eq__(other)

def __mul__(self, other):
if isinstance(other, Monomial):
return Monomial(*monomial_mul(self.data, other.data))
else:
raise TypeError("an instance of Monomial class expected, got %s" % other)

def __pow__(self, other):
n = int(other)

if not n:
return Monomial(*((0,)*len(self.data)))
elif n > 0:
data = self.data

for i in xrange(1, n):
data = monomial_mul(data, self.data)

return Monomial(*data)
else:
raise ValueError("a non-negative integer expected, got %s" % other)

def __div__(self, other):
if isinstance(other, Monomial):
result = monomial_div(self.data, other.data)

if result is not None:
return Monomial(*result)
else:
raise ExactQuotientFailed(self, other)
else:
raise TypeError("an instance of Monomial class expected, got %s" % other)

__floordiv__ = __truediv__ = __div__

def gcd(self, other):
"""Greatest common divisor of monomials. """
if isinstance(other, Monomial):
return Monomial(*monomial_gcd(self.data, other.data))
else:
raise TypeError("an instance of Monomial class expected, got %s" % other)

def lcm(self, other):
"""Least common multiple of monomials. """
if isinstance(other, Monomial):
return Monomial(*monomial_lcm(self.data, other.data))
else:
raise TypeError("an instance of Monomial class expected, got %s" % other)

@classmethod
def max(cls, *monomials):
"""Returns maximal degree for each variable in a set of monomials. """
return Monomial(*monomial_max(*[ monomial.data for monomial in monomials ]))

@classmethod
def min(cls, *monomials):
"""Returns minimal degree for each variable in a set of monomials. """
return Monomial(*monomial_min(*[ monomial.data for monomial in monomials ]))