SymPy PermutationGroup 完全指南置换群构造、BSGS 算法与群论计算实战【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy导读本文以 SymPy 组合学模块中sympy.combinatorics.perm_groups的PermutationGroup类为核心系统讲解如何在纯 Python 的计算机代数系统 SymPy 中构造置换群、进行元素与子群判定、计算轨道与稳定子以及利用 Schreier–Sims 算法BSGS高效计算群阶、陪集分解与结构性质。读完本文你将掌握从魔方旋转群到对称群/交错群判定的完整实战技能并能理解这些算法在 perm_groups.py 中的底层实现。一、模块定位SymPy 组合学中的置换群引擎PermutationGroup定义于 sympy/combinatorics/perm_groups.py是 SymPy 组合学sympy.combinatorics子系统中用于表示和计算有限置换群的核心类。它继承自 SymPy 表达式基类Basic因此群对象可以无缝融入 SymPy 的符号体系。其官方文档入口位于 doc/src/modules/combinatorics/perm_groups.rst由 Sphinx autodoc 从类的 docstring 自动生成这也意味着类内部丰富的文档字符串约 5599 行源码本身就是权威参考。在组合学模块的文档体系中PermutationGroup与其他组件协同工作均收录于 doc/src/modules/combinatorics/index.rstpermutations.rst —— 置换Permutation与轮换Cycle是本模块的输入原子perm_groups.rst —— 置换群本文主题named_groups.rst —— 预置的经典群对称群、交错群、循环群、二面体群等polyhedron.rst —— 多面体可将置换群用于刻画几何对象的对称性util.rst 与 testutil.rst —— 底层的 BSGS 工具函数与验证工具。二、构造置换群从生成元到群对象2.1 基本构造PermutationGroup([p1, p2, ..., pn])返回由这些置换生成闭包的置换群。生成元可以是Permutation、Cycle或它们的列表from sympy.combinatorics import Permutation, PermutationGroup a Permutation(1, 2, 3) # 一个 3-轮换 G PermutationGroup(a) G.degree # 3置换的作用域大小 len(G) # 1生成元个数 G.order() # 2群的阶即元素个数 list(G.generate()) # [(2), (2)(0 1)]2.2 构造器细节源码视角查看 perm_groups.py 的__new__构造器做了如下规范化处理空参数PermutationGroup()默认生成仅含恒等置换的平凡群混合类型参数中若含Cycle会先统一转换为Permutation度不一致若各生成元的size作用域大小不同默认取最大值作为群的degree也可通过关键字degree显式指定去重dupsTrue默认时按数组形式去重保留互异的生成元恒等元清理若传入多个生成元会剔除恒等置换单个恒等置换则保留。类的初始化__init__中还预置了一批惰性求值的缓存属性_order、_is_abelian、_is_transitive、_base、_strong_gens等所有计算结果都会被缓存多次查询不重复计算。2.3 经典示例2×2 魔方的旋转群官方 docstring 以 2×2 魔方为例。定义前、右、底三个面的旋转对 24 个贴纸位置的作用from sympy.combinatorics import Permutation, PermutationGroup F Permutation(2, 19, 21, 8)(3, 17, 20, 10)(4, 6, 7, 5) R Permutation(1, 5, 21, 14)(3, 7, 23, 12)(8, 10, 11, 9) D Permutation(6, 18, 14, 10)(7, 19, 15, 11)(20, 22, 23, 21) G PermutationGroup(F, R, D) G.order() # 3674160 —— 2×2 魔方可达状态数仅由三个面旋转生成的群其阶正好等于 2×2 魔方的全部可达状态数 3,674,160这说明置换群天然适合建模组合对象的状态空间——这正是本模块的典型应用场景之一。2.4 与 Polyhedron 协同追踪被移动的对象置换群可以交给Polyhedron用于追踪几何对象的顶点。官方示例演示了最基本的情形from sympy.combinatorics import Permutation, PermutationGroup, Polyhedron a Permutation(2, 1) b Permutation(1, 0) G PermutationGroup(a, b) P Polyhedron(list(ABC), pgroupG) P.corners # (A, B, C) P.rotate(0) # 施加第 0 个置换 P.corners # (A, C, B) P.reset() P.corners # (A, B, C)也可以直接用make_perm把一组生成元的组合作用到可迭代对象上P10 G.make_perm([0, 1]) P10(ABC) # [C, A, B]更多细节见 polyhedron.rst。三、基本属性degree、order、generators 与 elements属性/方法含义源码位置G.degree置换的作用域大小点的个数degree 属性G.order()群的阶即群中置换的个数order()len(G)生成元的个数__len__G.generators生成元列表generators 属性G.elements全部元素惰性枚举并缓存elements 属性G.identity恒等置换identity 属性G[i]第 i 个生成元__getitem__order() 的实现是 BSGS 的经典应用它并非暴力枚举全部元素而是先判断是否已知为对称群/交错群直接返回n!或n!/2否则计算各基本轨道横截集的长度之积m prod([len(x) for x in self.basic_transversals])这正是 Schreier–Sims 算法给出的阶公式——基本横截集长度的乘积等于群阶。参见 order() 实现。a Permutation([1, 0, 2]) G PermutationGroup([a]) G.degree # 3 len(G) # 1 G.order() # 2 p PermutationGroup(Permutation(1, 3), Permutation(1, 2)) p.elements # [(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 2)] —— 恰为 S_3 的 6 个元素四、成员判定与群间关系4.1contains判断置换是否属于群G.contains(g)判断g是否是G的元素。它底层复用coset_factor——能完成陪集分解即为群元素若g恰是某个生成元则直接短路返回True。strictFalse时允许对g的尺寸做适配a Permutation(1, 2) b Permutation(2, 3, 1) G PermutationGroup(a, b, degree5) G.contains(G[0]) # True G.contains(Permutation([[2, 3]], size5)) # True G.contains(Permutation(4)(0, 1, 2, 3)) # False H PermutationGroup(Permutation(5)) H.contains(Permutation(3)) # False尺寸不同 H.contains(Permutation(3), strictFalse) # True自动 resize注意与G.has(g)的区别contains判断的是群元素代数意义has判断的是生成元列表成员结构意义见 contains() 源码。4.2equals两个群是否相等生成同一闭包equals不比较生成元列表而是逐项互查生成元属于对方群p Permutation(0, 1, 2, 3, 4, 5) G PermutationGroup([p, p**2]) H PermutationGroup([p**2, p]) G.generators H.generators # False顺序不同 G.equals(H) # True闭包相同实现见 equals()。4.3 子群与指数、正规子群G.is_subgroup(H)判断G是否为H的子群G.index(H)返回指数[G : H] |G|/|H|要求H是G的子群G.is_normal(H)判断G是否为H的正规子群只需检查对H的生成元共轭后仍落在G内见 is_normal()。a Permutation(1, 2, 3) G PermutationGroup([a]) H PermutationGroup([Permutation(3)]) G.index(H) # 3 G1 PermutationGroup([a, Permutation([2, 0, 1])]) G1.is_normal(G) # True4.4 直积G * HG * H返回两个群的直积通过把第二个群的下标整体平移实现——若G作用在n1个点上、H作用在n2个点上则G*H作用在n1n2个点上from sympy.combinatorics.named_groups import CyclicGroup G CyclicGroup(5) H G * G H # PermutationGroup([(9)(0 1 2 3 4), (5 6 7 8 9)]) H.order() # 25实现见__mul__。注意若乘以单个Permutation则返回的是陪集对象Coset(other, self, dir)见下文第七节。五、轨道与稳定子群作用的核心工具5.1 轨道orbit与轨道分解orbitsG.orbit(alpha)返回点alpha的轨道{g(α) | g ∈ G}算法复杂度为O(|Orb| * r)r为生成元个数当alpha是点列表时action参数有三种语义union各点轨道的并、tuples按有序元组作用、sets按集合作用G.orbits()返回按最小元素排序的所有轨道分解。a Permutation([1, 2, 0, 4, 5, 6, 3]) G PermutationGroup([a]) G.orbit(0) # {0, 1, 2} G.orbit([0, 4], union) # {0, 1, 2, 3, 4, 5, 6} a Permutation(1, 5)(2, 3)(4, 0, 6) b Permutation(1, 5)(3, 4)(2, 6, 0) G PermutationGroup([a, b]) G.orbits() # [{0, 2, 3, 4, 6}, {1, 5}]5.2 稳定子stabilizer与逐点稳定子G.stabilizer(alpha)返回稳定子群G_α {g ∈ G | g(α) α}G.pointwise_stabilizer(points)对一组点同时保持不动的逐点稳定子。from sympy.combinatorics.named_groups import DihedralGroup G DihedralGroup(6) G.stabilizer(5) # PermutationGroup([(5)(0 4)(1 3)])5.3 轨道代表元与横截集G.orbit_rep(alpha, beta)返回把alpha送到beta的一个群元素若beta不在轨道中则返回False基于 Schreier 向量实现见 orbit_rep()G.orbit_transversal(alpha, pairsFalse)返回轨道的一个横截集{g_β | g_β(α) β}pairsTrue时返回(β, g_β)对列表G.schreier_vector(alpha)为轨道构造 Schreier 向量——它记录每个轨道点由哪个生成元首次到达从而支持快速找回代表元置换。注意向量依赖生成元顺序且用None表示不在轨道中见 schreier_vector()。from sympy.combinatorics.named_groups import AlternatingGroup G AlternatingGroup(5) G.orbit_rep(0, 4) # (0 4 1 2 3) G DihedralGroup(6) G.orbit_transversal(0) # [(5), (0 1 2 3 4 5), (0 5)(1 4)(2 3), (0 2 4)(1 3 5), (5)(0 4)(1 3), (0 3)(1 4)(2 5)] a Permutation([2, 4, 6, 3, 1, 5, 0]) b Permutation([0, 1, 3, 5, 4, 6, 2]) G PermutationGroup([a, b]) G.schreier_vector(0) # [-1, None, 0, 1, None, 1, 0]六、Schreier–Sims 算法与 BSGS置换群计算的基石BSGSBase and Strong Generating Set基与强生成集是置换群算法中最核心的数据结构。SymPy 的整套高阶查询阶、成员判定、陪集分解、随机元素都建立在它之上。6.1 概念基Base点序列B (b_1, ..., b_k)使得除恒等置换外没有任何群元素同时固定这些点强生成集SGS相对基B的生成集S要求每个逐点稳定子G^{(i1)} G_{b_1,...,b_i}都由S中属于它的元素生成基本稳定子链G G_{b_1} G_{b_1,b_2} ... 1。6.2 计算入口与缓存属性G.schreier_sims()运行增量式 Schreier–Sims 算法实现并把结果写入四个缓存属性此后以下属性可被直接读取首次访问时自动触发计算属性含义示例SymmetricGroup(4)G.base基[b_1, ..., b_k][0, 1, 2]G.strong_gens强生成集[(0 1 2 3), (0 3)(1 2), (1 3)]G.basic_orbits第 i 个基本轨道点b_i在G^{(i)}下的轨道[[0, 1, 2, 3], [1, 2, 3], [2, 3]]G.basic_stabilizers基本稳定子链G^{(i)}的群对象列表见下文示例G.basic_transversals基本横截集列表的每个元素是一个字典键为轨道点值为代表元置换见下文示例from sympy.combinatorics.named_groups import SymmetricGroup, AlternatingGroup S SymmetricGroup(4) S.basic_orbits # [[0, 1, 2, 3], [1, 2, 3], [2, 3]] A AlternatingGroup(4) A.base # [0, 1] for g in A.basic_stabilizers: print(g) # PermutationGroup([(3)(0 1 2), (1 2 3)]) # PermutationGroup([(1 2 3)]) A.basic_transversals # [{0: (3), 1: (3)(0 1 2), 2: (3)(0 2 1), 3: (0 3 1)}, # {1: (3), 2: (1 2 3), 3: (1 3 2)}]6.3 增量式实现与baseswapschreier_sims_incremental(baseNone, gensNone, slp_dictFalse)增量式版本可传入预设基并可返回强生成元 → 原始生成元的直线程序SLP字典供generator_product使用baseswap(base, strong_gens, pos, randomizedFalse, ...)交换基中相邻的两个点并重算强生成集返回(base, strong_gens)。默认的随机化版本是 Las Vegas 类型的结果一定正确耗时随机确定性版本见 baseswap() 的注释源码还指出教材 [1] 伪代码第 3 行的一个笔误。randomizedFalse的确定性示例from sympy.combinatorics.testutil import _verify_bsgs S SymmetricGroup(4) S.schreier_sims() base, gens S.baseswap(S.base, S.strong_gens, 1, randomizedFalse) base # [0, 2, 1] # 验证 swap 后仍是合法 BSGS S1 PermutationGroup(gens) _verify_bsgs(S1, base, gens) # True6.4 模块级工具函数除类方法外perm_groups.py 底部 还暴露了一组供内部复用的模块级函数_orbit、_orbits、_orbit_transversal、_stabilizer它们操作度 生成元数组的低层表示不依赖群对象状态是类方法的无缓存版本。七、陪集分解coset_factor、rank 与 unrank基于 BSGSSymPy 可以把任意群元素分解为取自各基本横截集的代表元之积这是成员判定与随机取样的基础。7.1coset_factor(g)若g ∈ G可写为g f[n]*...*f[1]*f[0]其中n len(G.base)f[i]取自第 i 个基本横截集若g ∉ G返回[]。factor_indexTrue时返回各因子在基本轨道中的下标便于对照basic_transversals还原a Permutation(0, 1, 3, 7, 6, 4)(2, 5) b Permutation(0, 1, 3, 2)(4, 5, 7, 6) G PermutationGroup([a, b]) g Permutation(7)(1, 2, 4)(3, 6, 5) G.contains(g) # True f G.coset_factor(g) f[2] * f[1] * f[0] g # True f1 G.coset_factor(g, True) # [0, 4, 4] tr G.basic_transversals f[0] tr[0][f1[0]] # True因子与下标一一对应 c Permutation(5, 6, 7) G.coset_factor(c) # []不属于群7.2coset_rank/coset_unrankcoset_rank(g)返回g在按陪集分解的字典序枚举中的序号与generate(methodcoset)顺序一致不属于群则返回Nonecoset_unrank(rank)coset_rank的逆运算0 rank order之外返回None。c Permutation(7)(2, 4)(3, 5) G.coset_rank(c) # 16 G.coset_unrank(16) # (7)(2 4)(3 5)7.3 群级陪集与陪集表G.coset_transversal(H)子群H的右陪集横截集G.coset_table(H)构造关于子群H的陪集表G.coset_representative(g, H)g所在陪集的代表元模块底部的Coset(g, H, GNone, dir)类封装单个左/右陪集G * perm的返回类型即为此类。Coset.is_left_coset/is_right_coset与as_list()可查询陪集属性见 Coset 类。八、枚举群元素generate / generate_dimino / generate_schreier_simsG.generate(methodcoset)是元素迭代器入口method二选一coset基于 Schreier–Sims 陪集表示按coset_rank顺序生成generate_schreier_sims适合大群、需先跑 BSGSdiminoDimino 算法从恒等元出发逐生成元扩张generate_dimino实现源自 AXIOM 系统的硕士论文算法。两者都支持afTrue以数组形式输出置换a Permutation([0, 2, 1, 3]) b Permutation([0, 2, 3, 1]) G PermutationGroup([a, b]) list(G.generate_dimino(afTrue)) # [[0, 1, 2, 3], [0, 2, 1, 3], [0, 2, 3, 1], # [0, 1, 3, 2], [0, 3, 2, 1], [0, 3, 1, 2]] list(G.generate_schreier_sims(afTrue)) # [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 2, 1], # [0, 1, 3, 2], [0, 2, 3, 1], [0, 3, 1, 2]]G.elements属性即list(self.generate())的缓存结果。此外G.generator_product(g, originalTrue)还能把元素表示为原始生成元的乘积内部利用 BSGS 的 SLP 记录见 generator_product()。九、群论性质判定从可解性到对称性PermutationGroup提供了丰富的一元判定属性绝大多数带缓存。下表汇总并给出源码位置属性判定内容关键实现点源码is_abelian交换群两两生成元可交换生成元两两检查_af_commutes_withL1788is_cyclic循环群基于max_div与元素阶的充要条件L3203is_dihedral二面体群基于is_cyclic与换位子结构L3290is_symmetric/is_alternating对称群 / 交错群精确小阶用阶判定大阶用蒙特卡洛 奇偶性L3074 / L3133is_alt_sym(eps0.05)对称/交错群的蒙特卡洛测试快速但非精确单侧蒙特卡洛错判概率 ≤ epsL1980is_transitive(strictTrue)传递群检查是否只有一个轨道L2396transitivity_degree多重传递度k递归检查 k 重传递L4316is_primitive/minimal_blocks本原群 / 最小块系Atkinson 算法 union-find并查集按秩合并与路径压缩L2133 / L2196is_perfect完全群等于其导群equals(derived_subgroup())L1768is_nilpotent幂零群下中心列终止于平凡群基于lower_central_seriesL2041is_solvable可解群基于导群列 / 换位子结构L2279is_trivial平凡群生成元是否全为恒等L2447is_polycyclic多循环群基于可解性与有限性L2377蒙特卡洛细节is_alt_sym对度 ≥ 8 的传递群使用单侧蒙特卡洛——回答True必然正确回答False出错的概率不超过eps默认 0.05。其理论依据是若传递群含有一个长度介于n/2与n-2之间的素数循环则该群必为对称群或交错群而对称/交错群中满足该性质的元素占比约为log(2)/log(n)。实现见_eval_is_alt_sym_monte_carlo与is_alt_sym的说明。相比之下is_symmetric/is_alternating在小阶8直接比对阶在大阶时先用蒙特卡洛缩小范围再用朴素阶判定补全且能区分对称与交错通过生成元的奇偶性。from sympy.combinatorics import Permutation, PermutationGroup, CyclicGroup, SymmetricGroup from sympy.combinatorics.named_groups import DihedralGroup # 交换性 a Permutation([0, 2, 1]); b Permutation([1, 0, 2]) PermutationGroup([a, b]).is_abelian # False PermutationGroup([a]).is_abelian # True # 对称 / 交错 SymmetricGroup(5).is_symmetric # True PermutationGroup(Permutation(0,1,2,3,4), Permutation(2,3)).is_symmetric # True # 二面体、幂零、可解 DihedralGroup(10).is_alt_sym() # False CyclicGroup(6).is_nilpotent # True SymmetricGroup(5).is_nilpotent # False阿贝尔不变量G.abelian_invariants()返回有限阿贝尔群分解为素数幂循环群直积时的不变量列表平凡群约定为[]见 abelian_invariants()G.is_elementary(p)判定是否为初等阿贝尔 p-群每个非平凡元素阶为p。G PermutationGroup([Permutation([0, 2, 1]), Permutation([1, 0, 2])]) G.abelian_invariants() # [2] CyclicGroup(7).abelian_invariants() # [7]十、群结构算法中心、导群、合成列与 Sylow 子群方法功能源码center()群的中心Z(G)L940centralizer(other)中心化子C_G(S)L978commutator(G, H)换位子群[G, H]L1097derived_subgroup()导群换位子子群L1461derived_series()导群列G G_0 G_1 ...L1412lower_central_series()下中心列L2466composition_series()合成列每个因子为单群L732normal_closure(other, k10)正规闭包L2780sylow_subgroup(p)p-Sylow 子群L4511quotient_group(N)商群G/NL5115presentation(eliminate_gensTrue)群的有限表现FpGroupL4960strong_presentation()基于强生成集的有限表现L4834polycyclic_group()多循环表示L5071character_table()特征标表L5151conjugacy_class(x)/conjugacy_classes()共轭类L2632 / L2692molien(xNone)Molien 级数用于表示论/不变量理论L2723subgroup(gens)/subgroup_search(prop, ...)子群构造与回溯搜索满足性质的子群L4051 / L4063典型演示——导群列与合成列from sympy.combinatorics.named_groups import SymmetricGroup, AlternatingGroup, CyclicGroup A AlternatingGroup(5) len(A.derived_series()) # 1A5 是单群导群列立即终止 S SymmetricGroup(4) len(S.derived_series()) # 4 S.derived_series()[1].is_subgroup(AlternatingGroup(4)) # True S.derived_series()[2].is_subgroup(DihedralGroup(2)) # True # 合成列从 2-Sylow / 3-Sylow 与循环群得到阶的递减链 S12 SymmetricGroup(12) C S12.sylow_subgroup(2).composition_series() [H.order() for H in C] # [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1] C S12.sylow_subgroup(3).composition_series() [H.order() for H in C] # [243, 81, 27, 9, 3, 1] C CyclicGroup(12).composition_series() [H.order() for H in C] # [12, 6, 3, 1]十一、随机元素product replacement 算法PermutationGroup提供三层随机取样接口G.random(afFalse)随机返回一个群元素基于已随机的生成元列表G.random_pr(gen_count11, iterations50)product replacement乘积替换算法。初始化时构造长度为max(gen_count, |S|)的生成元列表R并追加一个累加器恒等元每次迭代随机取R中两个非累加器元素g, h把g替换为{gh, g·h⁻¹, hg, h⁻¹·g}中随机一个再让累加器乘以新g并返回。理论上迭代足够多次后元素在G上趋于均匀分布工程上建议n 50, r 11见_random_pr_init的说明G.random_stab(alpha, ...)返回稳定子G_α中的随机元素。G PermutationGroup(Permutation(0,1,2,3,4), Permutation(0,1)(2,3)(4)) G.random_pr() # 每次返回群内一个近似均匀的随机置换这类随机取样是is_alt_sym蒙特卡洛测试、schreier_sims_random、subgroup_search等概率算法的基础。十二、其他群类型SymmetricPermutationGroup 与 Coset同一文件底部还定义了两个辅助类SymmetricPermutationGroup(deg)对称群S_deg的惰性表示——不显式枚举全部生成元而是重载__contains__、order()、identity、degree直接按定义回答适合作为大阶对称群的高效引用。参见 SymmetricPermutationGroupCoset(g, H, GNone, dir)单个陪集gH或Hg的封装dir控制左/右G * perm即产生右陪集。见 Coset 类。十三、测试与验证质量保证体系模块配备了两层验证手段单元测试sympy/combinatorics/tests/test_perm_groups.py 中共 67 个测试函数覆盖构造去重test_identity_generators_dups_false、阶与枚举test_order、test_generate、轨道/稳定子test_stabilizer、test_orbits、test_schreier_vector、陪集test_coset_rank、test_coset_factor、BSGStest_schreier_sims_incremental、test_baseswap、test_schreier_sims_random、群性质test_is_alt_sym、test_is_solvable、test_minimal_block以及魔方案例test_rubik、test_rubik1。验证工具sympy/combinatorics/testutil.py 中的_verify_bsgs可独立校验某个(base, strong_gens)是否为合法 BSGSdocs 示例与测试均用它做正确性断言。由于类继承自BasicPermutationGroup对象在 SymPy 的等式比较、哈希、copy等基础设施中行为一致这也被test_equality、test_eq、test_property_aliasing等测试覆盖。十四、算法参考与延伸阅读PermutationGroup的实现参考了计算群论领域的两本权威专著类 docstring 的 References 一节列出的 [1][2] 文献D. Holt, B. Eick, E. OBrien 著Handbook of Computational Group Theory覆盖 BSGS、product replacement、本原性判定等Á. Seress 著Permutation Group Algorithms覆盖稳定子链、随机算法、蒙特卡洛方法的理论分析。如需进一步探索可继续阅读同目录下的 permutations.rst置换与轮换的运算细节、named_groups.rst现成的群构造入口、fp_groups.rst有限表现群与presentation()输出对接以及 character_table.rst特征标表。结语PermutationGroup是 SymPy 组合学模块中以生成元描述、以算法推导一切的典范从一次PermutationGroup(F, R, D)的构造出发order()、contains()、orbit()、coset_factor()、sylow_subgroup()等数十个接口全部由 Schreier–Sims 算法BSGS这一个核心数据结构驱动。理解 BSGS 的原理基 强生成集 基本轨道/横截集就能举一反三地理解本模块几乎所有的计算接口。无论你是想建模魔方、研究几何对称、计算群的结构不变量还是在符号计算中嵌入群论逻辑perm_groups.py 都是可以直接取用的生产级实现。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考