haar_lib/algebra/
permutation.rs

1//! 配列の置換の合成
2pub use crate::algebra::traits::*;
3use crate::impl_algebra;
4
5/// 置換操作
6#[derive(Clone, Debug, Default, PartialEq)]
7pub struct Permutation {
8    value: Vec<usize>,
9}
10
11impl Permutation {
12    /// 恒等変換を返す。
13    pub fn id(n: usize) -> Self {
14        Self {
15            value: (0..n).collect(),
16        }
17    }
18
19    /// `i`番目の要素を返す。
20    pub fn get(&self, i: usize) -> usize {
21        self.value[i]
22    }
23
24    /// $b_i = a_{P_i}$を満たすbを返す。
25    pub fn apply<T: Clone>(&self, a: Vec<T>) -> Vec<T> {
26        self.value.iter().map(|&i| a[i].clone()).collect()
27    }
28
29    /// 操作を合成する。
30    pub fn compose(self, other: Self) -> Self {
31        let (a, b) = (self.value, other.value);
32        let n = a.len();
33        assert_eq!(a.len(), b.len());
34        Self {
35            value: (0..n).map(|i| a[b[i]]).collect(),
36        }
37    }
38
39    /// 逆操作を返す。
40    pub fn inv(self) -> Self {
41        let n = self.value.len();
42        let mut ret = vec![0; n];
43        for i in 0..n {
44            ret[self.value[i]] = i;
45        }
46        Self { value: ret }
47    }
48}
49
50impl TryFrom<Vec<usize>> for Permutation {
51    type Error = &'static str;
52
53    fn try_from(value: Vec<usize>) -> Result<Self, Self::Error> {
54        let mut check = vec![false; value.len()];
55
56        for &x in &value {
57            if x >= value.len() || check[x] {
58                return Err("0から`.len()｀未満の値からなる順列でなければならない。");
59            }
60            check[x] = true;
61        }
62        Ok(Self { value })
63    }
64}
65
66/// [`Permutation`]の合成
67#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
68pub struct Composition(pub usize);
69
70impl_algebra!(
71    Composition;
72    set: Permutation;
73    op: |_, a: Permutation, b: Permutation| a.compose(b);
74    inv: |_, a: Permutation| a.inv();
75    id: |s: &Self| Permutation::id(s.0);
76    assoc;
77);
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82    use rand::seq::SliceRandom;
83
84    #[test]
85    fn test() {
86        let mut rng = rand::thread_rng();
87
88        let n = 100;
89
90        let mut a = (0..n).collect::<Vec<_>>();
91        a.shuffle(&mut rng);
92        let a = Permutation::try_from(a).unwrap();
93
94        let b = a.clone().inv();
95
96        let m = Composition(n);
97        assert_eq!(m.op(a, b), m.id());
98    }
99}
haar_lib/algebra/permutation.rs

haar_lib/algebra/
permutation.rs
