2.6 置換群與 SymPy 的 combinatorics#

from sympy.combinatorics import Permutation

# 三種構造方式
a = Permutation(1, 2, 0)          # 像：0->1, 1->2, 2->0（3-循環）
b = Permutation([2, 0, 1])        # 由像的串列
c = Permutation(0, 1)(2, 3)       # 循環記號

print("a =", a, "， 迴路型 =", a.cyclic_form)
print("b =", b, "， c =", c)

# 運算與性質
print("a * b =", a * b)
print("a 的逆 =", ~a)
print("a 的階 =", a.order())
print("sgn(a) =", a.signature())
print("奇置換嗎 =", a.is_odd)
print("共軛：c * a * ~c =", c * a * ~c)

# 不相交循環分解與判斷
d = Permutation(0, 3, 1, 2)
print("d =", d, "， 分解 =", d.cyclic_form, "， 是對換嗎 =", d.cycle_structure == {2: 1})
print("d 是雙射 =", sorted(d.array_form) == list(range(d.size)))

a = (0 1 2) ， 迴路型 = [[0, 1, 2]]
b = (0 2 1) ， c = (0 1)(2 3)
a * b = (2)
a 的逆 = (0 2 1)
a 的階 = 3
sgn(a) = 1
奇置換嗎 = False
共軛：c * a * ~c = (0 3 1)
d = (0 3 1 2) ， 分解 = [[0, 3, 1, 2]] ， 是對換嗎 = False
d 是雙射 = True

from sympy.combinatorics import Permutation, PermutationGroup

S4 = PermutationGroup(Permutation(0, 1), Permutation(1, 2), Permutation(2, 3))
print("S_4 階 =", S4.order())                # 24

# 共軛類按迴路型分類
from collections import defaultdict
classes = defaultdict(list)
for g in S4.elements:
    cycle_lengths = tuple(sorted(
        len(c) for c in g.cyclic_form
    )) if g.cyclic_form else ()
    classes[(4 - sum(cycle_lengths)) and cycle_lengths].append(g)
    # 補上不動點：長度 1 的循環
for g in S4.elements:
    key = tuple(sorted([len(c) for c in g.cyclic_form] + [1] * (4 - sum(len(c) for c in g.cyclic_form))))
print("迴路型計數（含恆等）：")
counts = defaultdict(int)
for g in S4.elements:
    key = tuple(sorted([len(c) for c in g.cyclic_form] + [1]*(4 - sum(len(c) for c in g.cyclic_form))))
    counts[key] += 1
for key in sorted(counts):
    print("  迴路型", key, "：", counts[key], "個")
# 期望：(1,1,1,1):1, (1,1,2):6, (2,2):3, (1,3):8, (4):6

# A_4 與正規性
A4 = PermutationGroup(Permutation(0, 1, 2), Permutation(0, 1, 3))
print("A_4 階 =", A4.order())
print("A_4 正規於 S_4：", A4.is_normal(S4))

from sympy.combinatorics import Permutation, PermutationGroup
from sympy.combinatorics.named_groups import (CyclicGroup, DihedralGroup,
                                              AlternatingGroup, SymmetricGroup,
                                              AbelianGroup)

# 循環群與二面體群
C5 = CyclicGroup(5)
D5 = DihedralGroup(5)
print("C5 階 =", C5.order(), "； D5 階 =", D5.order())
print("D5 阿貝爾嗎 =", D5.is_abelian)        # False（n>=3）
print("D5 生成元：", D5.generators)

# 內建的對稱群、交錯群與有限交換群
print("S_5 階 =", SymmetricGroup(5).order())
print("A_5（內建）階 =", AlternatingGroup(5).order())
Z6xZ2 = AbelianGroup(6, 2)
print("Z/6 × Z/2 階 =", Z6xZ2.order(), "，阿貝爾 =", Z6xZ2.is_abelian)

# 交錯群與對稱群（用生成元定義大群時階由 Schreier–Sims 求出）
A5 = PermutationGroup(Permutation(0, 1, 2), Permutation(0, 1, 2, 3, 4))
print("A5 階 =", A5.order())                  # 60
print("A5 是單群嗎（檢查正規子群）…")

# 用 SymPy 檢查 A5 的正規子群只有平凡
def normal_subgroups(G):
    # 正規子群必為共軛類的聯集：枚舉共軛類的子集並檢查是否封閉
    classes = [set(C) for C in G.conjugacy_classes()]
    results = []
    for mask in range(1, 1 << len(classes)):
        S = set()
        for i, C in enumerate(classes):
            if mask >> i & 1:
                S |= C
        H = PermutationGroup(*S)
        if H.order() == len(S) and H.is_normal(G):
            results.append(H)
    return results

print("A_5 的正規子群階：", sorted({H.order() for H in normal_subgroups(A5)}))

C5 階 = 5 ； D5 階 = 10
D5 阿貝爾嗎 = False
D5 生成元： [Permutation(0, 1, 2, 3, 4), Permutation(0, 4)(1, 3)]
S_5 階 = 120
A_5（內建）階 = 60
Z/6 × Z/2 階 = 12 ，阿貝爾 = True
A5 階 = 60
A5 是單群嗎（檢查正規子群）…
A_5 的正規子群階： [1, 60]

from sympy.combinatorics import Permutation, PermutationGroup
import time

# 100 次對稱群 S_100：階為 100! （158 位數）——Schreier–Sims 不枚舉元素
S100 = PermutationGroup(*[Permutation(i, i+1) for i in range(99)])
t0 = time.time()
n = S100.order()
t1 = time.time()
print("S_100 的階是", n, "位數：", len(str(n)))
print("精確等於 100!：", n == __import__("math").factorial(100))
print("計算耗時：%.3f 秒" % (t1 - t0))

# 軌道：G 作用在 {0,...,99} 上當然傳遞
print("S_100 在 {0..99} 上的軌道：", S100.orbit(0))