algebraeon_groups/examples/
symmetric.rs

1use super::c2::C2;
2use crate::structure::{
3    AssociativeCompositionSignature, CompositionSignature, GroupSignature, IdentitySignature,
4    LeftCancellativeCompositionSignature, MetaCompositionSignature, MetaGroupSignature,
5    MetaIdentitySignature, MetaMonoidSignature, MonoidSignature,
6    RightCancellativeCompositionSignature, TryInverseSignature, TryLeftInverseSignature,
7    TryRightInverseSignature,
8};
9use algebraeon_sets::structure::{MetaType, SetSignature, Signature};
10use itertools::Itertools;
11use std::collections::HashMap;
12
13#[derive(Debug, Clone)]
14pub struct Cycle<const N: usize> {
15    cyc: Vec<usize>,
16}
17
18impl<const N: usize> Cycle<N> {
19    pub fn new(cyc: Vec<usize>) -> Result<Self, &'static str> {
20        let mut present = [false; N];
21        for i in &cyc {
22            if present[*i] {
23                return Err("Duplicate element in cycle");
24            }
25            present[*i] = true;
26        }
27        Ok(Self { cyc })
28    }
29
30    pub fn len(&self) -> usize {
31        self.cyc.len()
32    }
33
34    pub fn is_empty(&self) -> bool {
35        self.cyc.is_empty()
36    }
37}
38
39impl<const N: usize> std::convert::From<Cycle<N>> for Permutation<N> {
40    fn from(cyc: Cycle<N>) -> Self {
41        let mut perm = [0; N];
42        for i in 0..N {
43            perm[i] = i;
44        }
45        let n = cyc.cyc.len();
46        for i in 0..n {
47            perm[cyc.cyc[i]] = cyc.cyc[(i + 1) % n];
48        }
49        Self { perm }
50    }
51}
52
53#[derive(Debug, Clone, PartialEq, Eq, Hash)]
54pub struct Permutation<const N: usize> {
55    perm: [usize; N],
56}
57
58impl<const N: usize> TryFrom<super::super::permutation::Permutation> for Permutation<N> {
59    type Error = ();
60
61    fn try_from(value: super::super::permutation::Permutation) -> Result<Self, Self::Error> {
62        let n = value.n();
63        if N < n {
64            Err(())
65        } else {
66            let mut perm = [0; N];
67            for i in 0..N {
68                perm[i] = value.call(i);
69            }
70            Ok(Self { perm })
71        }
72    }
73}
74
75impl<const N: usize> Permutation<N> {
76    pub fn new(perm: [usize; N]) -> Result<Self, &'static str> {
77        //check that the numbers in forward are 0, 1, ..., n-1 in some order
78        let mut present = [false; N];
79        for i in &perm {
80            if *i >= N {
81                return Err("Permutation value out of range");
82            }
83            present[*i] = true;
84        }
85        for is_present in present {
86            if !is_present {
87                return Err("Not a valid permutation");
88            }
89        }
90        Ok(Self { perm })
91    }
92
93    pub fn new_from_cycles(cycles: Vec<Vec<usize>>) -> Result<Self, &'static str> {
94        let mut parsed_cycles = vec![];
95        for c in cycles {
96            parsed_cycles.push(Cycle::<N>::new(c)?);
97        }
98        Ok(Self::compose_list(
99            parsed_cycles
100                .into_iter()
101                .map(Into::<Permutation<N>>::into)
102                .collect(),
103        ))
104    }
105
106    pub fn call(&self, x: usize) -> Result<usize, &'static str> {
107        if x >= self.perm.len() {
108            return Err("argument too large");
109        }
110        Ok(self.perm[x])
111    }
112
113    pub fn sign(&self) -> C2 {
114        let mut s = C2::identity();
115        for i in 0..N {
116            for j in 0..i {
117                if (i < j) != (self.call(i) < self.call(j)) {
118                    s.compose_mut(&C2::Flip);
119                }
120            }
121        }
122        s
123    }
124
125    pub fn disjoint_cycles(&self) -> Vec<Cycle<N>> {
126        let mut missing: std::collections::HashSet<usize> = (0..N).collect();
127        let mut cycles = vec![];
128        while !missing.is_empty() {
129            let mut cycle = vec![];
130            let x = *missing.iter().min().unwrap();
131            let mut i = x;
132            loop {
133                cycle.push(i);
134                missing.remove(&i);
135                i = self.perm[i];
136                if i == x {
137                    break;
138                }
139            }
140            cycles.push(Cycle { cyc: cycle });
141        }
142        cycles
143    }
144
145    pub fn cycle_shape(&self) -> Vec<usize> {
146        let mut shape = self.disjoint_cycles().iter().map(Cycle::len).collect_vec();
147        shape.sort_unstable();
148        shape
149    }
150
151    pub fn all_permutations() -> impl Iterator<Item = Self> {
152        (0..N).permutations(N).map(|perm| Self {
153            perm: perm.try_into().unwrap(),
154        })
155    }
156
157    pub fn symmetric_composition_table() -> (
158        crate::composition_table::group::FiniteGroupMultiplicationTable,
159        Vec<Self>,
160        HashMap<Self, usize>,
161    ) {
162        Self::generated_finite_subgroup_table(Self::all_permutations().collect())
163    }
164
165    pub fn alternating_composition_table() -> (
166        crate::composition_table::group::FiniteGroupMultiplicationTable,
167        Vec<Self>,
168        HashMap<Self, usize>,
169    ) {
170        Self::generated_finite_subgroup_table(
171            Self::all_permutations()
172                .filter(|p| p.sign() == C2::Identity)
173                .collect(),
174        )
175    }
176}
177
178impl<const N: usize> std::fmt::Display for Permutation<N> {
179    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
180        let mut cycles = self.disjoint_cycles();
181        cycles.retain(|cycle| cycle.len() != 1);
182
183        if cycles.is_empty() {
184            f.write_str("()")?;
185        }
186
187        let string = cycles
188            .iter()
189            .map(|cycle| {
190                "(".to_owned()
191                    + &cycle
192                        .cyc
193                        .iter()
194                        .map(std::string::ToString::to_string)
195                        .collect::<Vec<String>>()
196                        .join(" ")
197                    + ")"
198            })
199            .collect::<Vec<String>>()
200            .join(" ");
201
202        f.write_str(string.as_str())
203    }
204}
205
206#[derive(Debug, Clone, PartialEq, Eq)]
207pub struct PermutationCanonicalStructure<const N: usize> {}
208
209impl<const N: usize> Signature for PermutationCanonicalStructure<N> {}
210
211impl<const N: usize> SetSignature for PermutationCanonicalStructure<N> {
212    type Set = Permutation<N>;
213
214    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
215        Ok(())
216    }
217}
218
219impl<const N: usize> MetaType for Permutation<N> {
220    type Signature = PermutationCanonicalStructure<N>;
221
222    fn structure() -> Self::Signature {
223        PermutationCanonicalStructure {}
224    }
225}
226
227impl<const N: usize> CompositionSignature for PermutationCanonicalStructure<N> {
228    fn compose(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
229        let mut comp_perm = [0; N];
230        for i in 0..N {
231            comp_perm[i] = a.perm[b.perm[i]];
232        }
233        Permutation { perm: comp_perm }
234    }
235}
236
237impl<const N: usize> AssociativeCompositionSignature for PermutationCanonicalStructure<N> {}
238
239impl<const N: usize> LeftCancellativeCompositionSignature for PermutationCanonicalStructure<N> {
240    fn try_left_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
241        Some(self.compose(&self.inverse(b), a))
242    }
243}
244
245impl<const N: usize> RightCancellativeCompositionSignature for PermutationCanonicalStructure<N> {
246    fn try_right_difference(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
247        Some(self.compose(a, &self.inverse(b)))
248    }
249}
250
251impl<const N: usize> IdentitySignature for PermutationCanonicalStructure<N> {
252    fn identity(&self) -> Self::Set {
253        let mut perm = [0; N];
254        for i in 0..N {
255            perm[i] = i;
256        }
257        Permutation { perm }
258    }
259}
260
261impl<const N: usize> MonoidSignature for PermutationCanonicalStructure<N> {}
262
263impl<const N: usize> TryLeftInverseSignature for PermutationCanonicalStructure<N> {
264    fn try_left_inverse(&self, a: &Self::Set) -> Option<Self::Set> {
265        Some(self.inverse(a))
266    }
267}
268
269impl<const N: usize> TryRightInverseSignature for PermutationCanonicalStructure<N> {
270    fn try_right_inverse(&self, a: &Self::Set) -> Option<Self::Set> {
271        Some(self.inverse(a))
272    }
273}
274
275impl<const N: usize> TryInverseSignature for PermutationCanonicalStructure<N> {
276    fn try_inverse(&self, a: &Self::Set) -> Option<Self::Set> {
277        Some(self.inverse(a))
278    }
279}
280
281impl<const N: usize> GroupSignature for PermutationCanonicalStructure<N> {
282    fn inverse(&self, a: &Self::Set) -> Self::Set {
283        let mut inv_perm = [0; N];
284        for (i, j) in a.perm.into_iter().enumerate() {
285            inv_perm[j] = i;
286        }
287        Permutation { perm: inv_perm }
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use super::*;
294
295    #[test]
296    fn test_composition() {
297        let a = Permutation::new([0, 2, 1]).unwrap();
298        let b = Permutation::new([1, 2, 0]).unwrap();
299        let c = Permutation::new([2, 1, 0]).unwrap();
300
301        println!("a = {}", a);
302        println!("b = {}", b);
303        println!("ab = {}", Permutation::compose(&a, &b));
304        println!("c = {}", c);
305
306        assert_eq!(Permutation::compose(&a, &b), c);
307    }
308
309    #[test]
310    fn test_sign() {
311        let a = Permutation::new([0, 2, 1]).unwrap();
312        let b = Permutation::new([1, 2, 0]).unwrap();
313        let c = Permutation::new([2, 1, 0]).unwrap();
314
315        println!("a = {}", a);
316        println!("b = {}", b);
317        println!("c = {}", c);
318
319        assert_eq!(a.sign(), C2::Flip);
320        assert_eq!(b.sign(), C2::Identity);
321        assert_eq!(c.sign(), C2::Flip);
322    }
323
324    #[test]
325    fn test_all_permutations() {
326        assert_eq!(Permutation::<0>::all_permutations().collect_vec().len(), 1);
327        assert_eq!(Permutation::<1>::all_permutations().collect_vec().len(), 1);
328        assert_eq!(Permutation::<2>::all_permutations().collect_vec().len(), 2);
329        assert_eq!(Permutation::<3>::all_permutations().collect_vec().len(), 6);
330        assert_eq!(Permutation::<4>::all_permutations().collect_vec().len(), 24);
331        assert_eq!(
332            Permutation::<5>::all_permutations().collect_vec().len(),
333            120
334        );
335    }
336}
algebraeon_groups/examples/symmetric.rs

algebraeon_groups/examples/
symmetric.rs
