haar_lib/algebra/
permutation.rs

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

haar_lib/algebra/
permutation.rs
