permutation_rs/group/
permutation.rs

1//! A permutation is a bijection of a set. Together with function composition
2//! this forms a group.
3//!
4//! # Examples
5//! A permutation is a `GroupElement` and can therefore be multiplied together.
6//! From the following computation it is clear that we compose from left to
7//! right.
8//!
9//! ```rust
10//! use std::collections::HashMap;
11//! use permutation_rs::group::GroupElement;
12//! use permutation_rs::group::permutation::Permutation;
13//!
14//! let mut left_image = HashMap::new();
15//! left_image.insert(0, 1);
16//! left_image.insert(1, 0);
17//! left_image.insert(2, 2);
18//! let left = Permutation::new(left_image);
19//!
20//! let mut right_image = HashMap::new();
21//! right_image.insert(0, 0);
22//! right_image.insert(1, 2);
23//! right_image.insert(2, 1);
24//! let right = Permutation::new(right_image);
25//!
26//! let answer = left.times(&right);
27//!
28//! let mut expected_image = HashMap::new();
29//! expected_image.insert(0, 2);
30//! expected_image.insert(1, 0);
31//! expected_image.insert(2, 1);
32//! let expected = Permutation::new(expected_image);
33//!
34//! assert_eq!(answer, expected);
35//! ```
36//!
37//! Writing the above permutations can get a bit unwieldy. You can use the
38//! `permute!` macro to alleviate the tedium a bit. For example, the `left`
39//! permutation could have been written like this
40//!
41//! ```rust
42//! # #[macro_use] extern crate permutation_rs;
43//! # use std::collections::HashMap;
44//! # use permutation_rs::group::permutation::Permutation;
45//! # fn main() {
46//! let left = permute!(
47//!     0, 1,
48//!     1, 0,
49//!     2, 2
50//! );
51//! # }
52//! ```
53
54use std::collections::HashMap;
55use std::collections::HashSet;
56use std::fmt;
57use std::fmt::Display;
58use super::{GroupElement, GroupAction};
59
60#[macro_export]
61macro_rules! permute {
62    ( $($from: expr, $to: expr),* ) => {
63        {
64            let mut permutation_images = HashMap::new();
65            $(
66                permutation_images.insert($from, $to);
67            )*
68            Permutation::new(permutation_images)
69        }
70    }
71}
72
73/// A permutation of the set 0..n for a suitable choice of n.
74#[derive(Debug, PartialEq, Clone)]
75pub struct Permutation {
76    n: usize,
77    images: HashMap<u64, u64>,
78}
79
80impl Permutation {
81    /// Create an permutation with a given image.
82    pub fn new(images: HashMap<u64, u64>) -> Permutation {
83        let n = images.len();
84        Permutation { images: images, n: n }
85    }
86}
87
88impl GroupElement for Permutation {
89    fn is_identity(&self) -> bool {
90        for i in 0..self.n {
91            let original = i as u64;
92            let image = self.images.get(&original).unwrap_or(&original).clone();
93            if image != original {
94                return false
95            }
96        }
97        true
98    }
99
100    fn times(&self, multiplicant: &Permutation) -> Permutation {
101        let max_n = if self.n > multiplicant.n { self.n } else { multiplicant.n };
102        let mut images = HashMap::new();
103        for i in 0..max_n {
104            let original = i as u64;
105            let mut image = self.images.get(&original).unwrap_or(&original).clone();
106            image = multiplicant.images.get(&image).unwrap_or(&image).clone();
107            images.insert(original, image);
108        }
109        Permutation::new(images)
110    }
111
112    fn inverse(&self) -> Permutation {
113        let mut images = HashMap::new();
114        for i in 0..self.n {
115            let original = i as u64;
116            let image = self.images.get(&original).unwrap_or(&original).clone();
117            images.insert(image, original);
118        }
119        Permutation::new(images)
120    }
121}
122
123impl GroupAction for Permutation {
124    type Domain = u64;
125
126    fn act_on(&self, original: &u64) -> u64 {
127        self.images.get(&original).unwrap_or(&original).clone()
128    }
129}
130
131impl Display for Permutation {
132    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
133        let cycles: Vec<Vec<u64>> = cycles(self.n, &self.images);
134        if cycles.len() > 0 {
135            for cycle in cycles {
136                let representations: Vec<String> =
137                    cycle
138                    .into_iter()
139                    .map(|element| format!("{}", element))
140                    .collect();
141                let representation: String = representations.join(" ");
142                write!(f, "(")?;
143                write!(f, "{}", representation)?;
144                write!(f, ")")?
145            }
146            write!(f, "")
147        } else {
148            write!(f, "Id")
149        }
150    }
151}
152
153fn cycles(n: usize, images: &HashMap<u64, u64>) -> Vec<Vec<u64>> {
154    let mut cycles = vec!();
155    let mut visited = HashSet::new();
156    for i in 0..n {
157        let original = i as u64;
158        if !visited.contains(&original) {
159            visited.insert(original.clone());
160            let mut cycle = vec!(original.clone());
161            let mut image = images.get(&original).unwrap_or(&original).clone();
162            while !visited.contains(&image) {
163                visited.insert(image.clone());
164                cycle.push(image.clone());
165                image = images.get(&image).unwrap_or(&image).clone();
166            }
167            if cycle.len() > 1 {
168                cycles.push(cycle);
169            }
170        }
171    }
172    cycles
173}
174
175#[cfg(test)]
176mod tests {
177    use std::collections::HashMap;
178    use super::super::{GroupElement, GroupAction};
179    use super::*;
180
181    #[test]
182    fn permutaion_should_know_when_it_is_the_identity() {
183        let mut not_identity_images = HashMap::new();
184        not_identity_images.insert(0u64, 1u64);
185        not_identity_images.insert(1u64, 0u64);
186        let not_identity = Permutation::new(not_identity_images);
187
188        assert!(!not_identity.is_identity());
189
190        let mut identity_images = HashMap::new();
191        identity_images.insert(0u64, 0u64);
192        identity_images.insert(1u64, 1u64);
193        let identity = Permutation::new(identity_images);
194
195        assert!(identity.is_identity());
196    }
197
198    #[test]
199    fn multiplication_should_be_from_left_to_right() {
200        let mut first_images = HashMap::new();
201        first_images.insert(0u64, 1u64);
202        first_images.insert(1u64, 0u64);
203        first_images.insert(2u64, 2u64);
204        let first = Permutation::new(first_images);
205
206        let mut second_images = HashMap::new();
207        second_images.insert(0u64, 0u64);
208        second_images.insert(1u64, 2u64);
209        second_images.insert(2u64, 1u64);
210        let second = Permutation::new(second_images);
211
212        let product = first.times(&second);
213
214        let mut expected_images = HashMap::new();
215        expected_images.insert(0u64, 2u64);
216        expected_images.insert(1u64, 0u64);
217        expected_images.insert(2u64, 1u64);
218        let expected = Permutation::new(expected_images);
219
220        assert_eq!(product, expected);
221    }
222
223    #[test]
224    fn inverse_should_multiply_to_identity() {
225        let mut first_images = HashMap::new();
226        first_images.insert(0u64, 1u64);
227        first_images.insert(1u64, 2u64);
228        first_images.insert(2u64, 0u64);
229        let first = Permutation::new(first_images);
230
231        let second = first.inverse();
232
233        let product = first.times(&second);
234
235        assert!(product.is_identity());
236    }
237
238    #[test]
239    fn permutation_should_act_upon_integers() {
240        let mut permutation_images = HashMap::new();
241        permutation_images.insert(0u64, 1u64);
242        permutation_images.insert(1u64, 2u64);
243        permutation_images.insert(2u64, 0u64);
244        let permutation = Permutation::new(permutation_images);
245
246        assert_eq!(permutation.act_on(&0u64), 1u64);
247        assert_eq!(permutation.act_on(&1u64), 2u64);
248        assert_eq!(permutation.act_on(&2u64), 0u64);
249    }
250
251    #[test]
252    fn permutation_should_display_correctly() {
253        let mut identity_images = HashMap::new();
254        identity_images.insert(0u64, 0u64);
255        identity_images.insert(1u64, 1u64);
256        let identity = Permutation::new(identity_images);
257
258        let mut permutation_images = HashMap::new();
259        permutation_images.insert(0u64, 1u64);
260        permutation_images.insert(1u64, 2u64);
261        permutation_images.insert(2u64, 0u64);
262        permutation_images.insert(3u64, 4u64);
263        permutation_images.insert(4u64, 3u64);
264        let permutation = Permutation::new(permutation_images);
265
266        assert_eq!("Id", format!("{}", identity));
267        assert_eq!("(0 1 2)(3 4)", format!("{}", permutation));
268    }
269}
permutation_rs/group/permutation.rs

permutation_rs/group/
permutation.rs
