対称群の部分群の簡単化
ソースコード
nachia/permutation/simplify-permitation-subgroup.hpp
主な機能
対称群 $S _ n$ の元の集合 $A$ が与えられたとき、それが生成する部分群 $G=\langle A\rangle$ について、別の集合 $B$ の要素を持つ 2 次元配列 B （ただしその要素は順列であるので、実際は 3 次元配列）を求める。ただし、以下の条件を満たすようにする。
- $\langle B\rangle =G$
- $
B[i][j]は以下の条件を満たす。- $i\lt k$ のとき、
B[i][j][k] == k B[i][j][i] < i- $j\neq k$ のとき、
B[i][j][i] != B[i][k][i]
- $i\lt k$ のとき、
-
B[i]の要素数を $X _ i$ と置くと、 $\prod _{i=0}^{n-1} X _ i$ は $G$ の要素数 $G $ に等しい。
関数 SimplifyPermutationSubgroup
// res.size() = n
// res[a][*].size() = (force_size_n ? n : (a+1))
// res[a][*][a] distinct
std::vector<std::vector<std::vector<int>>> SimplifyPermutationSubgroup(
int n,
std::vector<std::vector<int>> perm,
bool force_size_n = true
);
- $1 \leq n \leq 100$
permの各要素は長さ $n$ の配列であり、 $(0,1,\ldots ,n-1)$ の並べ替えである。- $m$ を
permの要素数とする。 $0\leq m\leq 10^8$ - $O(n^6+n^2m)$ 時間
- 返り値
Bは以下の条件を満たす。- $i\lt k$ のとき、
B[i][j][k] == k B[i][j][i] < i- $j\neq k$ のとき、
B[i][j][i] != B[i][k][i]
- $i\lt k$ のとき、
対称群の元を置換で表し、それを順列で表して処理する。仮に各順列を逆順列で置き換えても問題は変わらないため、どちらで捉えてもよい。
force_size_n が：
trueである場合、すべて要素数 $n$ とする。falseである場合、返り値BについてB[i]の要素B[i][j]の要素数を $i+1$ とする。
参考
- codeforces blog. “Permutation group basis construction (Schreier–Sims algorithm)” by adamant Link