permutation_rs/group/
free.rs

1//! A free group are the sequence of symbols and their inverses where there are
2//! no occurrences of a symbol and its inverse next to each other.
3//!
4//! # Examples
5//! Words can be multiplied to form more complex words. For example, if we have
6//! the word `abc` and multiply it with `c^-1bc`, we expect the result to be
7//! `ab^2c`.
8//!
9//! ```rust
10//! # use permutation_rs::group::GroupElement;
11//! # use permutation_rs::group::free::Word;
12//! let left = Word::new(vec![('a', 1), ('b', 1), ('c', 1)]);
13//! let right = Word::new(vec![('c', -1), ('b', 1), ('c', 1)]);
14//!
15//! let answer = left.times(&right);
16//!
17//! let expected = Word::new(vec![('a', 1), ('b', 2), ('c', 1)]);
18//! assert_eq!(answer, expected);
19//! ```
20use std::fmt;
21use std::fmt::Display;
22use super::GroupElement;
23
24/// The element of a free group.
25#[derive(Debug, PartialEq, Eq, Hash, Clone)]
26pub struct Word {
27    terms: Vec<(char, i64)>,
28}
29
30impl Word {
31    /// Create the identity element in a free group.
32    pub fn identity() -> Word {
33        Word::new(vec!())
34    }
35
36    /// Constructor which creates a single generator.
37    pub fn generator(symbol: char) -> Word {
38        Word::new(vec!((symbol, 1)))
39    }
40
41    /// Create a word with prescribed characters.
42    pub fn new(elements: Vec<(char, i64)>) -> Word {
43        Word { terms : normalize(&elements) }
44    }
45}
46
47
48fn normalize(elements: &Vec<(char, i64)>) -> Vec<(char, i64)> {
49    let mut not_normalized : Vec<(char, i64)> = vec!();
50    not_normalized.extend(elements);
51
52    if not_normalized.len() <= 1 {
53        not_normalized
54    } else {
55        let mut normalized : Vec<(char, i64)> = vec!();
56        let mut current: (char, i64) = not_normalized.get(0).expect("at least two elements").clone();
57        let mut index = 1;
58        while index < not_normalized.len() {
59            let primitive = not_normalized.get(index).expect("index within bound").clone();
60            if current.0 == primitive.0 {
61                current = (current.0.clone(), current.1 + primitive.1)
62            } else {
63                if current.1 != 0 {
64                    normalized.push(current)
65                } else {
66                    if !normalized.is_empty() {
67                        current = normalized.pop().expect("non-empty stack");
68                        continue;
69                    }
70                }
71                current = primitive
72            }
73            index += 1;
74        }
75        if current.1 != 0 {
76            normalized.push(current);
77        }
78
79        normalized
80    }
81}
82
83impl GroupElement for Word {
84    fn is_identity(&self) -> bool {
85        self.terms.len() == 0
86    }
87
88    fn times(&self, multiplicant: &Word) -> Word {
89        let mut terms: Vec<(char, i64)>= vec!();
90        terms.extend(&self.terms);
91        terms.extend(&multiplicant.terms);
92        let terms = normalize(&terms);
93        Word { terms: terms }
94    }
95
96    fn inverse(&self) -> Word {
97        let mut terms: Vec<(char, i64)>  = vec!();
98        terms.extend(&self.terms);
99        terms.reverse();
100        for element in terms.iter_mut() {
101            element.1 *= -1;
102        }
103        Word { terms: terms }
104    }
105}
106
107impl Display for Word {
108    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
109        if self.terms.len() > 0 {
110            for primitive in &self.terms {
111                write!(f, "{}^{}", primitive.0, primitive.1)?;
112            }
113            write!(f, "")
114        } else {
115            write!(f, "Id")
116        }
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::super::GroupElement;
123    use super::*;
124
125    #[test]
126    fn permutaion_should_know_when_it_is_the_identity() {
127        let not_identity = Word::generator('g');
128
129        assert!(!not_identity.is_identity());
130
131        let identity = Word::identity();
132
133        assert!(identity.is_identity());
134    }
135
136    #[test]
137    fn multiplication_should_be_from_left_to_right() {
138        let first = Word::generator('g');
139        let second = Word::generator('h');
140
141        let product = first.times(&second);
142
143        let expected = Word::new(vec!(('g', 1), ('h',1)));
144
145        assert_eq!(product, expected);
146    }
147
148    #[test]
149    fn inverse_should_multiply_to_identity() {
150        let first = Word::new(vec!(('g', 1), ('h',1)));
151
152        let second = first.inverse();
153
154        let product = first.times(&second);
155
156        assert!(product.is_identity());
157    }
158    
159    #[test]
160    fn word_should_display_correctly() {
161        let identity = Word::identity();
162
163        let word = Word::new(vec!(('x', 2), ('y', -3), ('x', -2), ('y', 3)));
164
165        assert_eq!("Id", format!("{}", identity));
166        assert_eq!("x^2y^-3x^-2y^3", format!("{}", word));
167    }
168}
permutation_rs/group/free.rs

permutation_rs/group/
free.rs
