algebraeon_groups/
group.rs

1use std::{
2    borrow::Borrow,
3    collections::{HashMap, HashSet},
4    fmt::Debug,
5    hash::Hash,
6};
7
8use itertools::Itertools;
9use malachite_base::num::{arithmetic::traits::UnsignedAbs, logic::traits::BitIterable};
10use malachite_nz::{integer::Integer, natural::Natural};
11
12pub trait Group: Debug + Clone + PartialEq + Eq {
13    fn identity() -> Self;
14
15    fn inverse(self) -> Self;
16    fn inverse_ref(&self) -> Self {
17        self.clone().inverse()
18    }
19
20    fn compose_mut(&mut self, other: &Self);
21    fn compose(mut a: Self, b: Self) -> Self {
22        Self::compose_mut(&mut a, &b);
23        a
24    }
25    fn compose_lref(a: &Self, b: Self) -> Self {
26        Self::compose(a.clone(), b)
27    }
28    fn compose_rref(a: Self, b: &Self) -> Self {
29        Self::compose(a, b.clone())
30    }
31    fn compose_refs(a: &Self, b: &Self) -> Self {
32        Self::compose(a.clone(), b.clone())
33    }
34
35    fn compose_list(elems: Vec<impl Borrow<Self>>) -> Self {
36        let mut ans = Self::identity();
37        for elem in elems {
38            ans.compose_mut(elem.borrow());
39        }
40        ans
41    }
42
43    fn nat_pow(&self, n: &Natural) -> Self {
44        if *n == 0 {
45            Self::identity()
46        } else if *n == 1 {
47            self.clone()
48        } else {
49            debug_assert!(*n >= 2);
50            let bits: Vec<_> = n.bits().collect();
51            let mut pows = vec![self.clone()];
52            while pows.len() < bits.len() {
53                pows.push(Self::compose_refs(
54                    &pows.last().unwrap(),
55                    &pows.last().unwrap(),
56                ));
57            }
58            let count = bits.len();
59            debug_assert_eq!(count, pows.len());
60            let mut ans = Self::identity();
61            for i in 0..count {
62                if bits[i] {
63                    ans.compose_mut(&pows[i]);
64                }
65            }
66            ans
67        }
68    }
69
70    fn int_pow(&self, n: &Integer) -> Self {
71        if *n == 0 {
72            Self::identity()
73        } else if *n > 0 {
74            self.nat_pow(&n.unsigned_abs())
75        } else {
76            self.nat_pow(&(-n).unsigned_abs()).inverse()
77        }
78    }
79
80    fn generated_finite_subgroup_table(
81        generators: Vec<Self>,
82    ) -> (
83        crate::composition_table::group::Group,
84        Vec<Self>,
85        HashMap<Self, usize>,
86    )
87    where
88        Self: std::hash::Hash,
89    {
90        let mut n = 0;
91        let mut idx_to_elem: Vec<Self> = vec![];
92        let mut elem_to_idx: HashMap<Self, usize> = HashMap::new();
93        let mut mul: Vec<Vec<Option<usize>>> = vec![];
94        let mut to_mul: Vec<(usize, usize)> = vec![];
95
96        macro_rules! add_elem {
97            ($elem : expr) => {{
98                debug_assert_eq!(idx_to_elem.len(), n);
99                debug_assert_eq!(elem_to_idx.len(), n);
100                debug_assert_eq!(mul.len(), n);
101                for m in &mul {
102                    debug_assert_eq!(m.len(), n);
103                }
104                if !elem_to_idx.contains_key(&$elem) {
105                    n += 1;
106                    let k = elem_to_idx.len();
107                    idx_to_elem.push($elem.clone());
108                    elem_to_idx.insert($elem, k);
109                    for i in (0..k) {
110                        mul[i].push(None);
111                        to_mul.push((i, k));
112                        to_mul.push((k, i));
113                    }
114                    mul.push(vec![None; k + 1]);
115                    to_mul.push((k, k));
116                    k
117                } else {
118                    *elem_to_idx.get(&$elem).unwrap()
119                }
120            }};
121        }
122
123        add_elem!(Self::identity());
124        for gen in generators {
125            add_elem!(gen);
126        }
127        while !to_mul.is_empty() {
128            let (i, j) = to_mul.pop().unwrap().clone();
129            let k = add_elem!(Self::compose_refs(&idx_to_elem[i], &idx_to_elem[j]));
130            debug_assert!(mul[i][j].is_none());
131            mul[i][j] = Some(k);
132        }
133        drop(to_mul);
134        let mul = mul
135            .into_iter()
136            .map(|m| m.into_iter().map(|x| x.unwrap()).collect_vec())
137            .collect_vec();
138        let inv = idx_to_elem
139            .iter()
140            .map(|elem| *elem_to_idx.get(&Self::inverse_ref(elem)).unwrap())
141            .collect_vec();
142
143        let grp = crate::composition_table::group::Group::new_unchecked(n, 0, inv, mul, None, None);
144
145        #[cfg(debug_assertions)]
146        grp.check_state().unwrap();
147
148        (grp, idx_to_elem, elem_to_idx)
149    }
150
151    fn generated_finite_subgroup(gens: Vec<Self>) -> FiniteSubgroup<Self>
152    where
153        Self: Hash,
154    {
155        //generate subgroup by adding all generated elements
156        let mut sg = HashSet::new();
157        sg.insert(Self::identity());
158
159        let mut boundary = vec![Self::identity()];
160        let mut next_boundary = vec![];
161        let mut y;
162        while boundary.len() > 0 {
163            println!("{}", sg.len());
164            for x in &boundary {
165                for g in &gens {
166                    y = Self::compose_refs(x, g);
167                    if !sg.contains(&y) {
168                        sg.insert(y.clone());
169                        next_boundary.push(y);
170                    }
171                }
172            }
173            boundary = next_boundary.clone();
174            next_boundary = vec![];
175        }
176
177        FiniteSubgroup {
178            elems: sg.into_iter().collect(),
179        }
180    }
181}
182
183pub trait Pow<ExpT> {
184    fn pow(&self, exp: ExpT) -> Self;
185}
186impl<G: Group> Pow<Natural> for G {
187    fn pow(&self, exp: Natural) -> Self {
188        self.nat_pow(&exp)
189    }
190}
191impl<G: Group> Pow<u8> for G {
192    fn pow(&self, exp: u8) -> Self {
193        self.nat_pow(&Natural::from(exp))
194    }
195}
196impl<G: Group> Pow<u16> for G {
197    fn pow(&self, exp: u16) -> Self {
198        self.nat_pow(&Natural::from(exp))
199    }
200}
201impl<G: Group> Pow<u32> for G {
202    fn pow(&self, exp: u32) -> Self {
203        self.nat_pow(&Natural::from(exp))
204    }
205}
206impl<G: Group> Pow<u64> for G {
207    fn pow(&self, exp: u64) -> Self {
208        self.nat_pow(&Natural::from(exp))
209    }
210}
211impl<G: Group> Pow<Integer> for G {
212    fn pow(&self, exp: Integer) -> Self {
213        self.int_pow(&exp)
214    }
215}
216impl<G: Group> Pow<i8> for G {
217    fn pow(&self, exp: i8) -> Self {
218        self.int_pow(&Integer::from(exp))
219    }
220}
221impl<G: Group> Pow<i16> for G {
222    fn pow(&self, exp: i16) -> Self {
223        self.int_pow(&Integer::from(exp))
224    }
225}
226impl<G: Group> Pow<i32> for G {
227    fn pow(&self, exp: i32) -> Self {
228        self.int_pow(&Integer::from(exp))
229    }
230}
231impl<G: Group> Pow<i64> for G {
232    fn pow(&self, exp: i64) -> Self {
233        self.int_pow(&Integer::from(exp))
234    }
235}
236
237#[derive(Debug, Clone)]
238pub struct FiniteSubgroup<G: Group> {
239    elems: Vec<G>,
240}
241
242impl<G: Group> FiniteSubgroup<G> {
243    pub fn size(&self) -> usize {
244        self.elems.len()
245    }
246
247    pub fn elements(&self) -> impl Iterator<Item = &G> {
248        self.elems.iter()
249    }
250}
algebraeon_groups/group.rs

algebraeon_groups/
group.rs
