permutation-rs 3.0.0

//! A module that provides various group related calculations.

use std::collections::VecDeque;
use super::GroupElement;
use super::permutation::Permutation;

/// Calculates the permutations generated by a set of generators.
///
/// Note that it uses a naive implementation that stores every permutation it
/// visits.
pub fn elements_generated_by(generators: &Vec<Permutation>) -> Vec<Permutation> {
    let mut elements: Vec<Permutation> = vec!();
    let mut to_visit: VecDeque<Permutation> = VecDeque::new();
    to_visit.push_back(identity(generators));

    while !to_visit.is_empty() {
        let element = to_visit.pop_front().unwrap();
        elements.push(element.clone());

        for ref g in generators {
            let next = element.times(g);
            if !elements.contains(&next) && !to_visit.contains(&next) {
                to_visit.push_back(next);
            }
        }
    }

    elements
}

/// Calculate an identity element for a set of generators. Assume that set is
/// non empty, panics otherwise.
pub fn identity<G>(generators: &Vec<G>) -> G where G: GroupElement {
    let g = generators.get(0).expect("at least one generator");
    let inverse = g.inverse();
    g.times(&inverse)
}


/// Calculate the nth factorial number.
///
/// The n! is defined as n * (n-1) * ... * 1
pub fn fact(m: u64) -> u64 {
    (1..m)
        .map(|n| n + 1)
        .fold(1u64, |acc, n| acc * n)
}

#[cfg(test)]
mod tests {
    use std::collections::HashMap;
    use super::super::GroupElement;
    use super::super::permutation::Permutation;
    use super::*;

    #[test]
    fn elements_generated_by_should_calculate_group_elements() {
        let mut rotation_images = HashMap::new();
        rotation_images.insert(0u64, 1u64);
        rotation_images.insert(1u64, 2u64);
        rotation_images.insert(2u64, 0u64);
        let rotation = Permutation::new(rotation_images);
        let id = rotation.times(&rotation.inverse());

        let elements = elements_generated_by(&vec!(rotation.clone()));

        assert!(elements.contains(&id));
        assert!(elements.contains(&rotation));
        assert!(elements.contains(&rotation.inverse()));
    }

    #[test]
    fn factorial() {
        assert_eq!(fact(1), 1);
        assert_eq!(fact(2), 2);
        assert_eq!(fact(3), 6);
        assert_eq!(fact(4), 24);
    }
}