本ライブラリの群の実装について

本ライブラリのいくつかのデータ構造では、一般の群で内部の演算が抽象化されているものがあります。そのようなデータ構造はSrc/Algebra/Group/*.hpp内のクラスや、それらと同様の実装をしたクラスをテンプレート引数で渡すことで利用することができます。

そもそも群とは

参考: Wikipedia

集合 $S$ と $S$ 上の二項演算 $f:\ S\times S\to S$ の組 $(S, f)$ は以下の条件を満たす時、群といいます。

• 結合則 $(\forall a, b, c\in S)[f(a, f(b, c)) = f(f(a, b), c)]$ を満たす
• ある要素 $e\in S$ が存在して、 $(\forall a\in S)[f(a, e) = f(e, a) = a]$ を満たす (このような $e$ を $S$ の単位元と呼ぶ)
• $S$ の全ての要素について逆元が存在する。すなわち $(\forall a\in S)(\exists b\in S)[f(a, b) = f(b, a) = e]$ を満たす。

本ライブラリでの実装

どのクラスも、基本的には以下のような枠組みで実装されています。

template <class T>
class Group {
    using Element = T;
    static constexpr T identity() noexcept {
    
    }
    static constexpr T operation(const T& l, const T& r) noexcept {
        
    }
    static constexpr T inverse(const T& v) noexcept {
    
    }
};

template引数 T

上の説明でいう、 $S$ です。例えば $32$ bitで収まる範囲で足し算をしたい時は int型やzawa::i32 (= std::int32_t)型を引数に入れることになります。

using Element = T

データ構造等で群の型にアクセスする時に使います。必ず用意してください。

identity

上の説明でいう、単位元を返すメソッドです。引数をとらず、 T型の値を返り値とするメソッドである必要があります。

operation

上の説明でいう、二項演算です。 必ず T型の変数 $2$ つを引数にとり、 T型の値を返り値とするメソッドである必要があります。

noexceptは無くても大丈夫です

inverse

上の説明でいう、逆元を返すメソッドです。必ず T型の変数 $1$ つを引数にとり、 T 型の値を帰り値とするメソッドである必要があります。

参考

• 代数的構造を乗せるデータ構造の設計について
  • 本ライブラリのデータ構造はこちらのブログの E の実装を参考に設計しています。