haar_lib/algebra/
dihedral.rs

1//! 二面体群 $D_n$
2//!
3//! # Problems
4//! - <https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0390>
5
6pub use crate::algebra::traits::*;
7use crate::impl_algebra;
8
9/// 対称変換
10#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
11pub enum Sym {
12    /// 回転
13    R(usize),
14    /// 鏡映
15    S(usize),
16}
17
18use Sym::{R, S};
19
20/// 二面体群$D_n$の元
21#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
22pub struct Dihedral {
23    size: usize,
24    value: Sym,
25}
26
27impl Dihedral {
28    /// 元の合成
29    pub fn compose(self, b: Self) -> Self {
30        let n = self.size;
31        assert_eq!(b.size, self.size);
32
33        let value = match (self.value, b.value) {
34            (R(x), R(y)) => R((x + y) % n),
35            (R(x), S(y)) => S((n + y - x) % n),
36            (S(x), R(y)) => S((x + y) % n),
37            (S(x), S(y)) => R((n + y - x) % n),
38        };
39
40        Self { size: n, value }
41    }
42
43    /// 単位元
44    pub fn id(size: usize) -> Self {
45        Self { size, value: R(0) }
46    }
47
48    /// 逆元
49    pub fn inv(self) -> Self {
50        let Self { size, value } = self;
51        let value = match value {
52            R(x) => R(if x == 0 { 0 } else { size - x }),
53            S(_) => value,
54        };
55        Self { size, value }
56    }
57
58    /// $D_n$の回転を表す元$R_i$を返す。
59    pub fn r(i: usize, n: usize) -> Self {
60        assert!(n > 0);
61        assert!(i < n);
62        Self {
63            size: n,
64            value: R(i),
65        }
66    }
67
68    /// $D_n$の鏡映を表す元$S_i$を返す。
69    pub fn s(i: usize, n: usize) -> Self {
70        assert!(n > 0);
71        assert!(i < n);
72        Self {
73            size: n,
74            value: S(i),
75        }
76    }
77}
78
79/// 二面体群$D_n$の元の合成
80#[derive(Clone, Copy, Debug)]
81pub struct Composition(usize);
82impl Composition {
83    /// 位数`2n`の二面体群を作る。
84    pub fn new(n: usize) -> Self {
85        assert!(n >= 1);
86        Self(n)
87    }
88}
89
90impl_algebra!(Composition; set: Dihedral;
91    op: |_, a: Dihedral, b: Dihedral| a.compose(b);
92    id: |s: &Self| Dihedral::id(s.0);
93    inv: |_, a: Dihedral| a.inv();
94    assoc;
95);
haar_lib/algebra/dihedral.rs

haar_lib/algebra/
dihedral.rs
