permutation_rs/group/
calculation.rs

1//! A module that provides various group related calculations.
2
3use std::collections::VecDeque;
4use super::GroupElement;
5use super::permutation::Permutation;
6
7/// Calculates the permutations generated by a set of generators.
8///
9/// Note that it uses a naive implementation that stores every permutation it
10/// visits.
11pub fn elements_generated_by(generators: &Vec<Permutation>) -> Vec<Permutation> {
12    let mut elements: Vec<Permutation> = vec!();
13    let mut to_visit: VecDeque<Permutation> = VecDeque::new();
14    to_visit.push_back(identity(generators));
15
16    while !to_visit.is_empty() {
17        let element = to_visit.pop_front().unwrap();
18        elements.push(element.clone());
19
20        for ref g in generators {
21            let next = element.times(g);
22            if !elements.contains(&next) && !to_visit.contains(&next) {
23                to_visit.push_back(next);
24            }
25        }
26    }
27
28    elements
29}
30
31/// Calculate an identity element for a set of generators. Assume that set is
32/// non empty, panics otherwise.
33pub fn identity<G>(generators: &Vec<G>) -> G where G: GroupElement {
34    let g = generators.get(0).expect("at least one generator");
35    let inverse = g.inverse();
36    g.times(&inverse)
37}
38
39
40/// Calculate the nth factorial number.
41///
42/// The n! is defined as n * (n-1) * ... * 1
43pub fn fact(m: u64) -> u64 {
44    (1..m)
45        .map(|n| n + 1)
46        .fold(1u64, |acc, n| acc * n)
47}
48
49#[cfg(test)]
50mod tests {
51    use std::collections::HashMap;
52    use super::super::GroupElement;
53    use super::super::permutation::Permutation;
54    use super::*;
55
56    #[test]
57    fn elements_generated_by_should_calculate_group_elements() {
58        let mut rotation_images = HashMap::new();
59        rotation_images.insert(0u64, 1u64);
60        rotation_images.insert(1u64, 2u64);
61        rotation_images.insert(2u64, 0u64);
62        let rotation = Permutation::new(rotation_images);
63        let id = rotation.times(&rotation.inverse());
64
65        let elements = elements_generated_by(&vec!(rotation.clone()));
66
67        assert!(elements.contains(&id));
68        assert!(elements.contains(&rotation));
69        assert!(elements.contains(&rotation.inverse()));
70    }
71
72    #[test]
73    fn factorial() {
74        assert_eq!(fact(1), 1);
75        assert_eq!(fact(2), 2);
76        assert_eq!(fact(3), 6);
77        assert_eq!(fact(4), 24);
78    }
79}
permutation_rs/group/calculation.rs

permutation_rs/group/
calculation.rs
