1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#[cfg(test)]
mod tests {
    use permutation;
    use permutation::Permutation;
    use std::ops::Mul;
    #[test]
    fn basics() {
        let p1 = Permutation::new(5);
        let p2 = Permutation::new(5);
        assert!(p1 == p2);
        let p3 = Permutation::new(6);
        assert!(p1 != p3);
    }

    #[test]
    fn math() {
        let id = Permutation::new(3);
        let p1 = Permutation::from_vec(vec![1, 0, 2]);
        let square = &p1 * &p1;
        assert!(square == id);
        let p2 = Permutation::from_vec(vec![0, 2, 1]);
        let prod = &p1 * &p2;
        assert!(prod == Permutation::from_vec(vec![2, 0, 1]));
    }
}


mod permutation {

    use std;
    #[derive(Eq, PartialEq, Clone)]
    pub struct Permutation {
        indices: Vec<usize>,
    }
    impl<'a, 'b> std::ops::Mul<&'b Permutation> for &'a Permutation {
        type Output = Permutation;
        fn mul(self, rhs: &'b Permutation) -> Self::Output {
            return Permutation::from_vec(self.apply_vec(&rhs.indices[..]));
        }
    }
    impl Permutation {
        pub fn from_vec(vec: Vec<usize>) -> Permutation {
            Permutation { indices: vec }
        }
        pub fn new(len: usize) -> Permutation {
            Permutation { indices: (0..len).collect() }
        }
        pub fn len(self) -> usize {
            return self.indices.len();
        }
        pub fn sort_by_key<B, F>(&mut self, f: F)
            where B: Ord,
                  F: FnMut(&usize) -> B
        {
            self.indices.sort_by_key(f);
        }
        pub fn apply_idx(&self, idx: usize) -> Option<usize> {
            return self.indices.get(idx).map(|&v| v);
        }
        pub fn apply_rev_idx(&self, idx: usize) -> Option<usize> {
            return self.indices.iter().position(|&v| v == idx);
        }
        pub fn apply_vec<T: Clone>(&self, vec: &[T]) -> Vec<T> {
            return self.indices
                       .iter()
                       .map(|&idx| vec[idx].clone())
                       .collect();
        }
        pub fn apply_rev_vec<T: Clone>(&self, vec: &[T]) -> Vec<T> {
            let mut other: Vec<T> = vec.to_vec();
            for (i, idx) in self.indices.iter().enumerate() {
                other[*idx] = vec[i].clone();
            }
            return other;
        }
    }

    pub fn sorted_permutation<T>(vec: Vec<T>) -> Permutation
        where T: Ord
    {
        let mut permutation = Permutation::new(vec.len());
        permutation.sort_by_key(|i| &vec[*i]);
        return permutation;
    }
}