GradedReverseLexOrder< VariableOrder > Struct Template Reference

Implements Graded reverse lexicographic order. More...

#include <drake/common/symbolic_monomial_util.h>

Public Member Functions

bool operator() (const Monomial &m1, const Monomial &m2)
 Returns true if m1 > m2 under the Graded reverse lexicographic order. More...

Detailed Description

template<typename VariableOrder>
struct drake::symbolic::GradedReverseLexOrder< VariableOrder >

Implements Graded reverse lexicographic order.

Template Parameters
VariableOrderVariableOrder{}(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

Member Function Documentation

bool operator() ( const Monomial m1,
const Monomial m2 

Returns true if m1 > m2 under the Graded reverse lexicographic order.

Here is the call graph for this function:

The documentation for this struct was generated from the following file: