Spaces:
Running
Running
| """Definitions of monomial orderings. """ | |
| from __future__ import annotations | |
| __all__ = ["lex", "grlex", "grevlex", "ilex", "igrlex", "igrevlex"] | |
| from sympy.core import Symbol | |
| from sympy.utilities.iterables import iterable | |
| class MonomialOrder: | |
| """Base class for monomial orderings. """ | |
| alias: str | None = None | |
| is_global: bool | None = None | |
| is_default = False | |
| def __repr__(self): | |
| return self.__class__.__name__ + "()" | |
| def __str__(self): | |
| return self.alias | |
| def __call__(self, monomial): | |
| raise NotImplementedError | |
| def __eq__(self, other): | |
| return self.__class__ == other.__class__ | |
| def __hash__(self): | |
| return hash(self.__class__) | |
| def __ne__(self, other): | |
| return not (self == other) | |
| class LexOrder(MonomialOrder): | |
| """Lexicographic order of monomials. """ | |
| alias = 'lex' | |
| is_global = True | |
| is_default = True | |
| def __call__(self, monomial): | |
| return monomial | |
| class GradedLexOrder(MonomialOrder): | |
| """Graded lexicographic order of monomials. """ | |
| alias = 'grlex' | |
| is_global = True | |
| def __call__(self, monomial): | |
| return (sum(monomial), monomial) | |
| class ReversedGradedLexOrder(MonomialOrder): | |
| """Reversed graded lexicographic order of monomials. """ | |
| alias = 'grevlex' | |
| is_global = True | |
| def __call__(self, monomial): | |
| return (sum(monomial), tuple(reversed([-m for m in monomial]))) | |
| class ProductOrder(MonomialOrder): | |
| """ | |
| A product order built from other monomial orders. | |
| Given (not necessarily total) orders O1, O2, ..., On, their product order | |
| P is defined as M1 > M2 iff there exists i such that O1(M1) = O2(M2), | |
| ..., Oi(M1) = Oi(M2), O{i+1}(M1) > O{i+1}(M2). | |
| Product orders are typically built from monomial orders on different sets | |
| of variables. | |
| ProductOrder is constructed by passing a list of pairs | |
| [(O1, L1), (O2, L2), ...] where Oi are MonomialOrders and Li are callables. | |
| Upon comparison, the Li are passed the total monomial, and should filter | |
| out the part of the monomial to pass to Oi. | |
| Examples | |
| ======== | |
| We can use a lexicographic order on x_1, x_2 and also on | |
| y_1, y_2, y_3, and their product on {x_i, y_i} as follows: | |
| >>> from sympy.polys.orderings import lex, grlex, ProductOrder | |
| >>> P = ProductOrder( | |
| ... (lex, lambda m: m[:2]), # lex order on x_1 and x_2 of monomial | |
| ... (grlex, lambda m: m[2:]) # grlex on y_1, y_2, y_3 | |
| ... ) | |
| >>> P((2, 1, 1, 0, 0)) > P((1, 10, 0, 2, 0)) | |
| True | |
| Here the exponent `2` of `x_1` in the first monomial | |
| (`x_1^2 x_2 y_1`) is bigger than the exponent `1` of `x_1` in the | |
| second monomial (`x_1 x_2^10 y_2^2`), so the first monomial is greater | |
| in the product ordering. | |
| >>> P((2, 1, 1, 0, 0)) < P((2, 1, 0, 2, 0)) | |
| True | |
| Here the exponents of `x_1` and `x_2` agree, so the grlex order on | |
| `y_1, y_2, y_3` is used to decide the ordering. In this case the monomial | |
| `y_2^2` is ordered larger than `y_1`, since for the grlex order the degree | |
| of the monomial is most important. | |
| """ | |
| def __init__(self, *args): | |
| self.args = args | |
| def __call__(self, monomial): | |
| return tuple(O(lamda(monomial)) for (O, lamda) in self.args) | |
| def __repr__(self): | |
| contents = [repr(x[0]) for x in self.args] | |
| return self.__class__.__name__ + '(' + ", ".join(contents) + ')' | |
| def __str__(self): | |
| contents = [str(x[0]) for x in self.args] | |
| return self.__class__.__name__ + '(' + ", ".join(contents) + ')' | |
| def __eq__(self, other): | |
| if not isinstance(other, ProductOrder): | |
| return False | |
| return self.args == other.args | |
| def __hash__(self): | |
| return hash((self.__class__, self.args)) | |
| def is_global(self): | |
| if all(o.is_global is True for o, _ in self.args): | |
| return True | |
| if all(o.is_global is False for o, _ in self.args): | |
| return False | |
| return None | |
| class InverseOrder(MonomialOrder): | |
| """ | |
| The "inverse" of another monomial order. | |
| If O is any monomial order, we can construct another monomial order iO | |
| such that `A >_{iO} B` if and only if `B >_O A`. This is useful for | |
| constructing local orders. | |
| Note that many algorithms only work with *global* orders. | |
| For example, in the inverse lexicographic order on a single variable `x`, | |
| high powers of `x` count as small: | |
| >>> from sympy.polys.orderings import lex, InverseOrder | |
| >>> ilex = InverseOrder(lex) | |
| >>> ilex((5,)) < ilex((0,)) | |
| True | |
| """ | |
| def __init__(self, O): | |
| self.O = O | |
| def __str__(self): | |
| return "i" + str(self.O) | |
| def __call__(self, monomial): | |
| def inv(l): | |
| if iterable(l): | |
| return tuple(inv(x) for x in l) | |
| return -l | |
| return inv(self.O(monomial)) | |
| def is_global(self): | |
| if self.O.is_global is True: | |
| return False | |
| if self.O.is_global is False: | |
| return True | |
| return None | |
| def __eq__(self, other): | |
| return isinstance(other, InverseOrder) and other.O == self.O | |
| def __hash__(self): | |
| return hash((self.__class__, self.O)) | |
| lex = LexOrder() | |
| grlex = GradedLexOrder() | |
| grevlex = ReversedGradedLexOrder() | |
| ilex = InverseOrder(lex) | |
| igrlex = InverseOrder(grlex) | |
| igrevlex = InverseOrder(grevlex) | |
| _monomial_key = { | |
| 'lex': lex, | |
| 'grlex': grlex, | |
| 'grevlex': grevlex, | |
| 'ilex': ilex, | |
| 'igrlex': igrlex, | |
| 'igrevlex': igrevlex | |
| } | |
| def monomial_key(order=None, gens=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 | |
| 4. ilex, igrlex, igrevlex - the corresponding inverse orders | |
| If the ``order`` 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 the ``gens`` input argument contains a list of generators, the | |
| resulting key function can be used to sort SymPy ``Expr`` objects. | |
| """ | |
| if order is None: | |
| order = lex | |
| if isinstance(order, Symbol): | |
| order = str(order) | |
| if isinstance(order, str): | |
| try: | |
| order = _monomial_key[order] | |
| except KeyError: | |
| raise ValueError("supported monomial orderings are 'lex', 'grlex' and 'grevlex', got %r" % order) | |
| if hasattr(order, '__call__'): | |
| if gens is not None: | |
| def _order(expr): | |
| return order(expr.as_poly(*gens).degree_list()) | |
| return _order | |
| return order | |
| else: | |
| raise ValueError("monomial ordering specification must be a string or a callable, got %s" % order) | |
| class _ItemGetter: | |
| """Helper class to return a subsequence of values.""" | |
| def __init__(self, seq): | |
| self.seq = tuple(seq) | |
| def __call__(self, m): | |
| return tuple(m[idx] for idx in self.seq) | |
| def __eq__(self, other): | |
| if not isinstance(other, _ItemGetter): | |
| return False | |
| return self.seq == other.seq | |
| def build_product_order(arg, gens): | |
| """ | |
| Build a monomial order on ``gens``. | |
| ``arg`` should be a tuple of iterables. The first element of each iterable | |
| should be a string or monomial order (will be passed to monomial_key), | |
| the others should be subsets of the generators. This function will build | |
| the corresponding product order. | |
| For example, build a product of two grlex orders: | |
| >>> from sympy.polys.orderings import build_product_order | |
| >>> from sympy.abc import x, y, z, t | |
| >>> O = build_product_order((("grlex", x, y), ("grlex", z, t)), [x, y, z, t]) | |
| >>> O((1, 2, 3, 4)) | |
| ((3, (1, 2)), (7, (3, 4))) | |
| """ | |
| gens2idx = {} | |
| for i, g in enumerate(gens): | |
| gens2idx[g] = i | |
| order = [] | |
| for expr in arg: | |
| name = expr[0] | |
| var = expr[1:] | |
| def makelambda(var): | |
| return _ItemGetter(gens2idx[g] for g in var) | |
| order.append((monomial_key(name), makelambda(var))) | |
| return ProductOrder(*order) | |