http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46279
Brief description:
给定长度为 N 的置换集合 S，|S| = M，求满足一下条件的集合 G 的最小的阶。
- $$S\subset G$$
- $$\forall \sigma, \tau \in G, \sigma \tau^{-1} \in G$$
Analysis:
…
“A subset H of the group G is a subgroup of G if and only if it is nonempty and closed under products and inverses. (The closure conditions mean the following: whenever a and b are in H, then ab and a−1 are also in H. These two conditions can be combined into one equivalent condition: whenever a and b are in H, then ab−1 is also in H.)"
http://en.wikipedia.org/wiki/Subgroup
包含 S 的最小的群即为 S 的生成子群。记 G = <S>，要求的既是 |<S>|。
我们用 Schreier – Sims 算法求出 <S> 的基 B。我们知道 B 定义了一个子群链。
$$! G = G^{[1]} \geq G^{[2]} \geq \ldots \geq G^{[m]} \geq G^{[m+1]} = 1 $$
由拉格朗日定理，
$$! |G| = \Pi_{i=1}^{m} |G^{[i]} : G^{[i+1]}| $$
而 G^[i] 中 G^[i+1] 的陪集个数就是 $$|R_i|$$。
陪集划分:
设 H 是 G 的子群，对任意的 a ∈ G，称 aH = {ah | h ∈ H} 为子群 H 的一个左陪集。称 Ha = {ha | h ∈ H} 为子群 H 的一个右陪集。
设 G 中 H 的所有左陪集形成的集合为 Sl, 所有右陪集的集合为 Sr，可以证明映射 aH -> Ha^{-1} 是 Sl 到 Sr 的一一映射。
定理 1：设 H 为 G 的子群，任给 H 的右陪集 Ha, Hb。要么 Ha = Hb，要么 Ha ∩ Hb = ∅。
这个定理说明了群 G 可以划分成两两不相交的右陪集的并，给我们一种分析和简化群结构的思路。
拉格朗日定理
记 [G: H] 表示 G 中子群 H 的不同右陪集的个数。用 1 表示只含单位元的子群，[G: 1] 表示 G 的阶。我们可以立即得到：[G : 1] = [G : H][H : 1]。
References:
对最换群有关算法的初步研究 by crx
Group 解题报告 by ftiasch
