HDU 4702. Group

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