1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//! Monomial orderings for Gröbner basis computation.
use std::cmp::Ordering;
/// A monomial ordering for multivariate polynomials.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum MonomialOrder {
/// Lexicographic order (Lex): x > y > z, compare exponents left-to-right.
Lex,
/// Graded lexicographic order (GrLex): total degree first, then Lex.
GrLex,
/// Graded reverse lexicographic order (GRevLex): total degree first, then reverse Lex.
#[default]
GRevLex,
}
impl MonomialOrder {
/// Compare two exponent vectors under this ordering.
/// Exponent vectors are indexed by variable (index 0 = first variable).
pub fn cmp(&self, a: &[u32], b: &[u32]) -> Ordering {
match self {
MonomialOrder::Lex => {
for (ai, bi) in a.iter().zip(b.iter()) {
let c = ai.cmp(bi);
if c != Ordering::Equal {
return c;
}
}
a.len().cmp(&b.len())
}
MonomialOrder::GrLex => {
let da: u32 = a.iter().sum();
let db: u32 = b.iter().sum();
match da.cmp(&db) {
Ordering::Equal => MonomialOrder::Lex.cmp(a, b),
c => c,
}
}
MonomialOrder::GRevLex => {
let da: u32 = a.iter().sum();
let db: u32 = b.iter().sum();
match da.cmp(&db) {
Ordering::Equal => {
for (ai, bi) in a.iter().rev().zip(b.iter().rev()) {
let c = bi.cmp(ai); // reversed!
if c != Ordering::Equal {
return c;
}
}
Ordering::Equal
}
c => c,
}
}
}
}
/// True for graded orders (GrLex, GRevLex) where total degree is the primary key.
///
/// For graded orders, LM(g) cannot divide a term of lower total degree, so the
/// degree-skip optimization in reduction is sound.
#[inline]
pub fn is_graded(self) -> bool {
matches!(self, MonomialOrder::GrLex | MonomialOrder::GRevLex)
}
/// Parse from a string: "lex", "grlex", "grevlex".
#[allow(clippy::should_implement_trait)]
pub fn from_str(s: &str) -> Option<Self> {
match s.to_lowercase().as_str() {
"lex" => Some(MonomialOrder::Lex),
"grlex" => Some(MonomialOrder::GrLex),
"grevlex" | "degrevlex" => Some(MonomialOrder::GRevLex),
_ => None,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn lex_order() {
let a = vec![2u32, 0, 0];
let b = vec![0u32, 1, 0];
assert_eq!(MonomialOrder::Lex.cmp(&a, &b), Ordering::Greater);
}
#[test]
fn grlex_order() {
let a = vec![2u32, 0];
let b = vec![1u32, 1];
assert_eq!(MonomialOrder::GrLex.cmp(&a, &b), Ordering::Greater);
}
#[test]
fn grevlex_order() {
let a = vec![2u32, 0, 0];
let b = vec![0u32, 0, 2];
assert_eq!(MonomialOrder::GRevLex.cmp(&a, &b), Ordering::Greater);
}
#[test]
fn from_str_works() {
assert_eq!(MonomialOrder::from_str("lex"), Some(MonomialOrder::Lex));
assert_eq!(MonomialOrder::from_str("grlex"), Some(MonomialOrder::GrLex));
assert_eq!(
MonomialOrder::from_str("grevlex"),
Some(MonomialOrder::GRevLex)
);
assert_eq!(
MonomialOrder::from_str("degrevlex"),
Some(MonomialOrder::GRevLex)
);
assert_eq!(MonomialOrder::from_str("unknown"), None);
}
}