Implements Graded reverse lexicographic order.
VariableOrder | VariableOrder{}(v1, v2) is true if v1 < v2. |
We first compare the total degree of the monomial; if there is a tie, then we use the lexicographical order as the tie breaker, but a monomial with higher order in lexicographical order is considered lower order in graded reverse lexicographical order.
Take MonomialBasis({x, y, z}, 2) as an example, with the order x > y > z. To get the graded reverse lexicographical order, we take the following steps:
First find all the monomials using the total degree. The monomials with degree 2 are {x^2, y^2, z^2, xy, xz, yz}. The monomials with degree 1 are {x, y, z}, and the monomials with degree 0 is {1}. To break the tie between monomials with the same total degree, first sort them in the reverse lexicographical order, namely x < y < z in the reverse lexicographical order. The lexicographical order compares two monomial by first comparing the exponent of the largest variable, if there is a tie then go forth to the second largest variable. Thus z^2 > zy >zx > y^2 > yx > x^2. Finally reverse the order as x^2 > xy > y^2 > xz > yz > z^2.
There is an introduction to monomial order in https://en.wikipedia.org/wiki/Monomial_order, and an introduction to graded reverse lexicographical order in https://en.wikipedia.org/wiki/Monomial_order#Graded_reverse_lexicographic_order
#include <drake/common/symbolic/monomial_util.h>
Public Member Functions | |
bool | operator() (const Monomial &m1, const Monomial &m2) const |
Returns true if m1 > m2 under the Graded reverse lexicographic order. More... | |
Returns true if m1 > m2 under the Graded reverse lexicographic order.