Coverage for /usr/lib/python3/dist-packages/sympy/polys/orderings.py: 53%
127 statements
« prev ^ index » next coverage.py v7.9.1, created at 2025-06-14 15:55 +0200
1"""Definitions of monomial orderings. """
3from __future__ import annotations
5__all__ = ["lex", "grlex", "grevlex", "ilex", "igrlex", "igrevlex"]
7from sympy.core import Symbol
8from sympy.utilities.iterables import iterable
10class MonomialOrder:
11 """Base class for monomial orderings. """
13 alias: str | None = None
14 is_global: bool | None = None
15 is_default = False
17 def __repr__(self):
18 return self.__class__.__name__ + "()"
20 def __str__(self):
21 return self.alias
23 def __call__(self, monomial):
24 raise NotImplementedError
26 def __eq__(self, other):
27 return self.__class__ == other.__class__
29 def __hash__(self):
30 return hash(self.__class__)
32 def __ne__(self, other):
33 return not (self == other)
35class LexOrder(MonomialOrder):
36 """Lexicographic order of monomials. """
38 alias = 'lex'
39 is_global = True
40 is_default = True
42 def __call__(self, monomial):
43 return monomial
45class GradedLexOrder(MonomialOrder):
46 """Graded lexicographic order of monomials. """
48 alias = 'grlex'
49 is_global = True
51 def __call__(self, monomial):
52 return (sum(monomial), monomial)
54class ReversedGradedLexOrder(MonomialOrder):
55 """Reversed graded lexicographic order of monomials. """
57 alias = 'grevlex'
58 is_global = True
60 def __call__(self, monomial):
61 return (sum(monomial), tuple(reversed([-m for m in monomial])))
63class ProductOrder(MonomialOrder):
64 """
65 A product order built from other monomial orders.
67 Given (not necessarily total) orders O1, O2, ..., On, their product order
68 P is defined as M1 > M2 iff there exists i such that O1(M1) = O2(M2),
69 ..., Oi(M1) = Oi(M2), O{i+1}(M1) > O{i+1}(M2).
71 Product orders are typically built from monomial orders on different sets
72 of variables.
74 ProductOrder is constructed by passing a list of pairs
75 [(O1, L1), (O2, L2), ...] where Oi are MonomialOrders and Li are callables.
76 Upon comparison, the Li are passed the total monomial, and should filter
77 out the part of the monomial to pass to Oi.
79 Examples
80 ========
82 We can use a lexicographic order on x_1, x_2 and also on
83 y_1, y_2, y_3, and their product on {x_i, y_i} as follows:
85 >>> from sympy.polys.orderings import lex, grlex, ProductOrder
86 >>> P = ProductOrder(
87 ... (lex, lambda m: m[:2]), # lex order on x_1 and x_2 of monomial
88 ... (grlex, lambda m: m[2:]) # grlex on y_1, y_2, y_3
89 ... )
90 >>> P((2, 1, 1, 0, 0)) > P((1, 10, 0, 2, 0))
91 True
93 Here the exponent `2` of `x_1` in the first monomial
94 (`x_1^2 x_2 y_1`) is bigger than the exponent `1` of `x_1` in the
95 second monomial (`x_1 x_2^10 y_2^2`), so the first monomial is greater
96 in the product ordering.
98 >>> P((2, 1, 1, 0, 0)) < P((2, 1, 0, 2, 0))
99 True
101 Here the exponents of `x_1` and `x_2` agree, so the grlex order on
102 `y_1, y_2, y_3` is used to decide the ordering. In this case the monomial
103 `y_2^2` is ordered larger than `y_1`, since for the grlex order the degree
104 of the monomial is most important.
105 """
107 def __init__(self, *args):
108 self.args = args
110 def __call__(self, monomial):
111 return tuple(O(lamda(monomial)) for (O, lamda) in self.args)
113 def __repr__(self):
114 contents = [repr(x[0]) for x in self.args]
115 return self.__class__.__name__ + '(' + ", ".join(contents) + ')'
117 def __str__(self):
118 contents = [str(x[0]) for x in self.args]
119 return self.__class__.__name__ + '(' + ", ".join(contents) + ')'
121 def __eq__(self, other):
122 if not isinstance(other, ProductOrder):
123 return False
124 return self.args == other.args
126 def __hash__(self):
127 return hash((self.__class__, self.args))
129 @property
130 def is_global(self):
131 if all(o.is_global is True for o, _ in self.args):
132 return True
133 if all(o.is_global is False for o, _ in self.args):
134 return False
135 return None
137class InverseOrder(MonomialOrder):
138 """
139 The "inverse" of another monomial order.
141 If O is any monomial order, we can construct another monomial order iO
142 such that `A >_{iO} B` if and only if `B >_O A`. This is useful for
143 constructing local orders.
145 Note that many algorithms only work with *global* orders.
147 For example, in the inverse lexicographic order on a single variable `x`,
148 high powers of `x` count as small:
150 >>> from sympy.polys.orderings import lex, InverseOrder
151 >>> ilex = InverseOrder(lex)
152 >>> ilex((5,)) < ilex((0,))
153 True
154 """
156 def __init__(self, O):
157 self.O = O
159 def __str__(self):
160 return "i" + str(self.O)
162 def __call__(self, monomial):
163 def inv(l):
164 if iterable(l):
165 return tuple(inv(x) for x in l)
166 return -l
167 return inv(self.O(monomial))
169 @property
170 def is_global(self):
171 if self.O.is_global is True:
172 return False
173 if self.O.is_global is False:
174 return True
175 return None
177 def __eq__(self, other):
178 return isinstance(other, InverseOrder) and other.O == self.O
180 def __hash__(self):
181 return hash((self.__class__, self.O))
183lex = LexOrder()
184grlex = GradedLexOrder()
185grevlex = ReversedGradedLexOrder()
186ilex = InverseOrder(lex)
187igrlex = InverseOrder(grlex)
188igrevlex = InverseOrder(grevlex)
190_monomial_key = {
191 'lex': lex,
192 'grlex': grlex,
193 'grevlex': grevlex,
194 'ilex': ilex,
195 'igrlex': igrlex,
196 'igrevlex': igrevlex
197}
199def monomial_key(order=None, gens=None):
200 """
201 Return a function defining admissible order on monomials.
203 The result of a call to :func:`monomial_key` is a function which should
204 be used as a key to :func:`sorted` built-in function, to provide order
205 in a set of monomials of the same length.
207 Currently supported monomial orderings are:
209 1. lex - lexicographic order (default)
210 2. grlex - graded lexicographic order
211 3. grevlex - reversed graded lexicographic order
212 4. ilex, igrlex, igrevlex - the corresponding inverse orders
214 If the ``order`` input argument is not a string but has ``__call__``
215 attribute, then it will pass through with an assumption that the
216 callable object defines an admissible order on monomials.
218 If the ``gens`` input argument contains a list of generators, the
219 resulting key function can be used to sort SymPy ``Expr`` objects.
221 """
222 if order is None:
223 order = lex
225 if isinstance(order, Symbol):
226 order = str(order)
228 if isinstance(order, str):
229 try:
230 order = _monomial_key[order]
231 except KeyError:
232 raise ValueError("supported monomial orderings are 'lex', 'grlex' and 'grevlex', got %r" % order)
233 if hasattr(order, '__call__'):
234 if gens is not None:
235 def _order(expr):
236 return order(expr.as_poly(*gens).degree_list())
237 return _order
238 return order
239 else:
240 raise ValueError("monomial ordering specification must be a string or a callable, got %s" % order)
242class _ItemGetter:
243 """Helper class to return a subsequence of values."""
245 def __init__(self, seq):
246 self.seq = tuple(seq)
248 def __call__(self, m):
249 return tuple(m[idx] for idx in self.seq)
251 def __eq__(self, other):
252 if not isinstance(other, _ItemGetter):
253 return False
254 return self.seq == other.seq
256def build_product_order(arg, gens):
257 """
258 Build a monomial order on ``gens``.
260 ``arg`` should be a tuple of iterables. The first element of each iterable
261 should be a string or monomial order (will be passed to monomial_key),
262 the others should be subsets of the generators. This function will build
263 the corresponding product order.
265 For example, build a product of two grlex orders:
267 >>> from sympy.polys.orderings import build_product_order
268 >>> from sympy.abc import x, y, z, t
270 >>> O = build_product_order((("grlex", x, y), ("grlex", z, t)), [x, y, z, t])
271 >>> O((1, 2, 3, 4))
272 ((3, (1, 2)), (7, (3, 4)))
274 """
275 gens2idx = {}
276 for i, g in enumerate(gens):
277 gens2idx[g] = i
278 order = []
279 for expr in arg:
280 name = expr[0]
281 var = expr[1:]
283 def makelambda(var):
284 return _ItemGetter(gens2idx[g] for g in var)
285 order.append((monomial_key(name), makelambda(var)))
286 return ProductOrder(*order)