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]。

http://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E5%AE%9A%E7%90%86_(%E7%BE%A4%E8%AB%96)

References:

对最换群有关算法的初步研究 by crx
Group 解题报告 by ftiasch

Posted by xiaodao
Category: 日常
Tags: 群论