SymPy 计算群论工具函数深度指南combinatorics.util 模块与 BSGS 算法实战【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy本文围绕 SymPy 的 combinatorics/util.py 模块展开系统讲解其内部为计算群论Computational Group Theory提供的八个核心工具函数从基base与强生成集strong generating set的组织到基本轨道、基本横截的计算再到置换筛选sifting与冗余生成元的剔除。读完本文你将理解这些函数在 Schreier-Sims 算法、陪集计算、正规闭包与对称/交错群判定等场景中的实际角色并能直接在 PermutationGroup 体系中复用它。一、模块定位BSGS 算法族的积木盒SymPy 的置换群功能核心位于 perm_groups.py而 combinatorics/util.py 则是支撑它的底层工具集。该模块的函数全部以下划线开头属于库内复用型基础设施但它们并非无人问津的内部细节——PermutationGroup的多个公开方法、以及张量规范型tensor canonical form算法 tensor_can.py都直接 import 并调用它们。从源码结构看这些函数共同服务于一套称为BSGS的核心数据结构。BSGS 是 Base 与 Strong Generating Set 的缩写其基本思想是基base一组点(b_1, ..., b_k)使得只有恒等置换同时固定它们基本稳定子basic stabilizersG^(i) G_{b_1,...,b_{i-1}}即逐点固定前i-1个基点的子群形成一条稳定子链G G^(1) ≥ G^(2) ≥ ... ≥ G^(k1) {e}强生成集strong generating set与基相容的一组生成元使得每个基本稳定子都由其中的相应子集生成。有了 BSGS群的阶、成员判定、陪集枚举等大量问题都可以转化为多项式时间的轨道计算。本文文档 util.rst 中列出的八个函数正是围绕 BSGS 的构造—分配—计算—精简—使用全流程设计的。二、快速上手安装与导入SymPy 是纯 Python 实现的计算机代数系统本模块仅依赖sympy.combinatorics.permutations与sympy.ntheory无第三方运行时依赖。可以从仓库根目录安装后使用pip install .然后即可导入模块并运行文中的示例 from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import _base_ordering S SymmetricGroup(4) S.schreier_sims() _base_ordering(S.base, S.degree) [0, 1, 2, 3]以下各节将逐一解析每个函数包括其参数、返回值、算法思想与源码级实现细节。三、核心函数逐一解析3.1_base_ordering(base, degree)为回溯搜索建立点序作用对点集{0, 1, ..., n-1}建立一种线性序使基点排在最前且按基的顺序排列。签名与返回接收base基与degree置换群的次数n返回列表base_ordering其中base_ordering[point]表示该点在序中的编号。算法核心见 util.py先把每个基点base[i]排在位置i再把不在基中的点按自然序依次接在后面。base_len len(base) ordering [0]*degree for i in range(base_len): ordering[base[i]] i current base_len for i in range(degree): if i not in base: ordering[i] current current 1 return ordering为什么要这样排序在回溯搜索backtrack search中需要定义点集上的关系≪使得基中靠前的点b_i排在靠后基点之前且任何基点都排在非基点之前。这样可以在陪集横截的构造中按base_ordering对元素排序、比较从而剪枝加速。此思想在 Holt、Eick、OBrien 的Handbook of Computational Group Theorypp. 108-132中有详细展开。实测用例来自 test_util.pybase [2, 4, 5] degree 7 assert _base_ordering(base, degree) [3, 4, 0, 5, 1, 2, 6]即基点 2、4、5 分别排在 0、1、2 位其余点 0、1、3、6 依次排在 3、4、5、6 位。调用方PermutationGroup.coset_transversal与_coset_representative见 perm_groups.py 与 L883用于按base_ordering[base[l]^x]排序横截元素、选取最小陪集代表元。3.2_check_cycles_alt_sym(perm)检测素数长循环作用判断置换中是否存在长度为素数p且满足n/2 p n-2的循环n为置换次数。这是PermutationGroup.is_alt_sym的辅助函数。理论基础群论与数论中的一个经典结果——若次数为n的传递群G含有一个长度为素数p、且n/2 p n-2的循环则G必为对称群或交错群见 perm_groups.py 的 Notes。实现要点util.py利用数组形式array_form沿j - af[j]追踪每个循环的长度只遍历前n//2个起点每个非平凡循环在到达n//2前必定已被遇到一旦发现满足条件的循环立即返回True否则返回False。示例源自文档 doctest from sympy.combinatorics.util import _check_cycles_alt_sym from sympy.combinatorics import Permutation a Permutation([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12]]) # n13 _check_cycles_alt_sym(a) False b Permutation([[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10]]) # n11 _check_cycles_alt_sym(b) True第一个例子中 11 长度循环满足11 13/2但11不小于n-2 11故不满足严格不等式p n-2返回False第二个例子中长度 7 的循环满足7/2 7 9且 7 为素数返回True。调用方_eval_is_alt_sym_monte_carloperm_groups.py在单侧蒙特卡洛测试中逐个检查随机抽样到的置换测试用例见 test_util.py其中perm1 [[0..6]]长度 7n10满足5 7 8判定为True。3.3_distribute_gens_by_base(base, gens)按基本稳定子分配生成元作用把一组生成元按固定前多少个基点分桶得到强生成集的稳定子链表示。返回长度为k len(base)的列表第i个元素是固定前i个基点的那些生成元故第 0 项等于gens本身若某级没有任何生成元固定相应基点则放入一个恒等置换占位保证每级非空。实现要点util.py对每个生成元gen从头扫描基点计算其最多连续固定多少个基点得到下标j随后把gen追加到stabs[0..j]中扫描结束后对剩余为空的下标填入恒等置换。示例源自文档 doctest from sympy.combinatorics.named_groups import DihedralGroup from sympy.combinatorics.util import _distribute_gens_by_base D DihedralGroup(3) D.schreier_sims() D.strong_gens [(0 1 2), (0 2), (1 2)] D.base [0, 1] _distribute_gens_by_base(D.base, D.strong_gens) [[(0 1 2), (0 2), (1 2)], [(1 2)]]调用方PermutationGroup.basic_stabilizers属性perm_groups.py、schreier_sims_incrementalL3707、normal_closureL2837以及张量规范型模块 tensor_can.py。此外 testutil.py 中的_verify_bsgs也用它来校验 BSGS 的正确性。3.4_handle_precomputed_bsgs(base, strong_gens, ...)补齐缺失的 BSGS 结构作用在已有基与强生成集的前提下按需补齐横截transversals、基本轨道basic orbits与按稳定子分配的强生成元避免重复计算。签名_handle_precomputed_bsgs(base, strong_gens, transversalsNone, basic_orbitsNone, strong_gens_distrNone)。返回三元组(transversals, basic_orbits, strong_gens_distr)。其补齐逻辑util.py是若strong_gens_distr为空调用_distribute_gens_by_base计算若transversals为空且basic_orbits也为空调用_orbits_transversals_from_bsgs一并计算若只有transversals为空则仅用transversals_onlyTrue计算横截若transversals已提供而basic_orbits为空则直接从横截字典的键提取轨道元素。示例源自文档 doctest对DihedralGroup(3)只传入basic_orbits D DihedralGroup(3) D.schreier_sims() _handle_precomputed_bsgs(D.base, D.strong_gens, ... basic_orbitsD.basic_orbits) ([{0: (2), 1: (0 1 2), 2: (0 2)}, {1: (2), 2: (1 2)}], [[0, 1, 2], [1, 2]], [[(0 1 2), (0 2), (1 2)], [(1 2)]])横截以字典列表形式给出第i个字典的键是基本轨道basic_orbits[i]中的点值是把base[i]送到该点的横截元素。调用方PermutationGroup.schreier_sims的内部路径_schreier_sims使用perm_groups.py它把用户传入的基、强生成元、横截、基本轨道统一整理为完整 BSGS 结构。测试见 test_util.py其中用AlternatingGroup(5)验证了横截元素确实把base[i]送到对应轨道点、且固定更靠前的基点并验证∏|basic_orbits[i]| |A|。3.5_orbits_transversals_from_bsgs(base, strong_gens_distr, ...)计算基本轨道与横截作用从基与已按稳定子分配的强生成元出发为每个基点计算基本轨道及其横截。签名_orbits_transversals_from_bsgs(base, strong_gens_distr, transversals_onlyFalse, slpFalse)。参数说明transversals_only默认False同时返回轨道与横截设为True时只返回横截列表slp默认False若为True额外返回一个字典列表记录每个横截元素相对strong_gens_distr[i]中生成元的生成子表示即生成元下标列表其乘积等于该横截元素这在需要记录群的元素表达式straight-line program时非常关键。实现要点util.py对每个基点base[i]调用perm_groups._orbit_transversal(degree, strong_gens_distr[i], base[i], pairsTrue, slpTrue)计算轨道横截对再转成字典。返回三种形态仅横截、(basic_orbits, transversals)、或(basic_orbits, transversals, slps)。示例源自文档 doctestSymmetricGroup(3) S SymmetricGroup(3) S.schreier_sims() strong_gens_distr _distribute_gens_by_base(S.base, S.strong_gens) (S.base, strong_gens_distr) ([0, 1], [[(0 1 2), (2)(0 1), (1 2)], [(1 2)]])调用方normal_closureperm_groups.py、_schreier_simsL3609此处传入slpTrue生成横截元素的生成子表示、coset_table相关路径L4167以及 tensor_can.py。测试 test_orbits_transversals_from_bsgs 验证了横截元素的正确性以及∏|basic_orbits[i]|等于群阶。3.6_remove_gens(base, strong_gens, ...)剔除冗余强生成元作用在保持相对于基仍是强生成集的前提下从强生成集中移除冗余生成元返回原集合的一个最小化子集。签名_remove_gens(base, strong_gens, basic_orbitsNone, strong_gens_distrNone)。若后两个参数未提供会先调用_distribute_gens_by_base与_orbit自动计算。算法思想util.py依据Handbook of Computational Group Theoryp.95从最高层稳定子向低层逆序遍历对每个生成元若它不固定下一层基点即不在更深的稳定子中则尝试把它从副本中删掉若删除后该层生成元生成的轨道仍覆盖basic_orbits[i]则确认删除——因为轨道未缩小说明它对该层是冗余的。示例源自文档 doctest并配合_verify_bsgs验证 from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import _remove_gens from sympy.combinatorics.testutil import _verify_bsgs S SymmetricGroup(15) base, strong_gens S.schreier_sims_incremental() new_gens _remove_gens(base, strong_gens) len(new_gens) 14 _verify_bsgs(S, base, new_gens) True测试覆盖test_remove_gens 分别对SymmetricGroup(10)、AlternatingGroup(7)、DihedralGroup(2)运行并断言_verify_bsgs通过说明精简后的集合仍是有效的 BSGS。3.7_strip(g, base, orbits, transversals)置换筛选sifting作用利用一个可能是部分的BSGS 结构尝试把置换g分解为标准形式。这一过程称为sifting筛选。签名_strip(g, base, orbits, transversals)其中orbits列表第i项是base[i]在某个隐含的基本稳定子下的轨道transversals与orbits对应的轨道横截字典列表。返回(h, level)二元组——h是筛选后剩下的置换level是筛选终止的层级。若成功h为恒等置换且level len(base) 1若失败某个轨道中找不到目标点或筛选结束不是恒等则返回中间态与失败层级。这两项信息对随机化 Schreier-Sims 算法至关重要失败的层级指明了需要在稳定子链的哪个位置补充新的强生成元见 perm_groups.py 的说明。实现要点util.py逐层处理对第i层取beta h(base[i])若beta base[i]说明已固定该点继续下一层若beta不在轨道中则筛选失败否则用横截元素u transversals[i][beta]左乘消除该层的贡献即h ← u⁻¹·h。示例源自文档 doctest from sympy.combinatorics import Permutation, SymmetricGroup from sympy.combinatorics.util import _strip S SymmetricGroup(5) S.schreier_sims() g Permutation([0, 2, 3, 1, 4]) _strip(g, S.base, S.basic_orbits, S.basic_transversals) ((4), 5)调用方normal_closureperm_groups.py用它判定共轭元素是否已落入当前生成子群schreier_sims_random用它筛选随机元素并据此修补稳定子链。测试 test_strip 用DihedralGroup(5)验证群内元素筛选后为恒等且层级为len(base)1群外元素要么保持自身、要么在中间层级失败。3.8_strong_gens_from_distr(strong_gens_distr)从分配结果还原强生成集作用把按基本稳定子分配的生成元列表压平为原始的强生成集。由于第 0 级稳定子即整个群G而任何固定了b_1的强生成元都同时出现在第 1 级中因此只需取第 0 级与第 1 级生成元的并集即可见 util.py 的实现。示例源自文档 doctest from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import (_strong_gens_from_distr, ... _distribute_gens_by_base) S SymmetricGroup(3) S.schreier_sims() S.strong_gens [(0 1 2), (2)(0 1), (1 2)] strong_gens_distr _distribute_gens_by_base(S.base, S.strong_gens) _strong_gens_from_distr(strong_gens_distr) [(0 1 2), (2)(0 1), (1 2)]调用方PermutationGroup.baseswapperm_groups.py在交换基中相邻两点后用它从更新过的分配结构重建强生成集。测试 test_strong_gens_from_distr 验证了去重并集的正确性。3.9 补充_strip_af——数组形式的优化版筛选虽然不在文档 util.rst 的 autofunction 列表中但源码中还有其高性能版本_strip_af(h, base, orbits, transversals, j, slp[], slps{})util.py全程使用数组形式array form避免反复构造Permutation对象参数j记录h已固定前j1个基点筛选从j1层开始跳过已知不动的部分若slp非空同时累积生成子表示对横截元素的表示取逆并前插用于schreier_sims_incremental的slp_dictTrue模式返回约定不同若筛选结果为恒等直接返回(False, base_len1)h u时短路否则返回(h, level)或(h, level, slp)。它是schreier_sims_incremental主循环中检查 Schreier 生成元是否落入下一稳定子的关键步骤perm_groups.py。四、在 PermutationGroup 中的调用链一张功能地图结合上文各函数的调用方可以整理出这张工具函数 → 公开 API的功能地图工具函数主要调用方perm_groups.py服务场景_base_orderingcoset_transversal(L821)、_coset_representative(L883)陪集横截排序、陪集代表元选取_check_cycles_alt_sym_eval_is_alt_sym_monte_carlo(L1976)is_alt_sym单侧蒙特卡洛判定_distribute_gens_by_basebasic_stabilizers(L693)、schreier_sims_incremental(L3707)、normal_closure(L2837)稳定子链组织、BSGS 构造_handle_precomputed_bsgsschreier_sims路径 (L565)BSGS 结构补齐_orbits_transversals_from_bsgs_schreier_sims(L3609)、normal_closure(L2839)、coset_table(L4167)轨道与横截计算_remove_gens由用户直接调用配合_verify_bsgs强生成集精简_stripnormal_closure(L2850)、schreier_sims_random(L3908)元素分解、随机算法筛选_strip_afschreier_sims_incremental(L3748)确定性 Schreier-Sims 主循环_strong_gens_from_distrbaseswap(L612)基交换后重建强生成集此外_distribute_gens_by_base与_orbits_transversals_from_bsgs还被 tensor_can.py 用于张量规范型算法中的双陪集计算体现了这些工具跨越了纯群论与表示论应用两个领域。五、一致性验证_verify_bsgs与测试保障这些工具函数的正确性由 tests/test_util.py 中的九组测试全面覆盖重点包括轨道横截一致性对basic_orbits[i]中每个元素el断言transversals[i]el el且该横截元素固定所有更靠前的基点群阶恢复断言∏|basic_orbits[i]| G.order()这正是 BSGS 计算群阶的核心公式筛选判定群内元素筛选后得恒等、层级为len(base)1群外元素要么原样返回要么在中间层级失败精简有效性_remove_gens的输出必须继续通过 testutil.py 中_verify_bsgs的严格校验。六、数学背景与文献指引模块内多处注释引用了计算群论的经典教材Holt、Eick、OBrien 合著的Handbook of Computational Group Theory相关页码sifting 算法见 pp. 89-90增量式 Schreier-Sims 见 pp. 90-93_remove_gens见 p.95随机化版本见 pp. 97-98回溯搜索与点序思想见 pp. 108-132对称/交错群判定的素数循环准则见 pp. 81-82。读者若想深入理解这些工具的来龙去脉可以对照该教材研读相应章节再回到本模块源码中印证。总结sympy.combinatorics.util是 SymPy 计算群论引擎的积木盒——它本身不提供面向终端用户的 API却以清晰的分层结构支撑起 Schreier-Sims 算法、陪集计算、正规闭包与群类型判定等核心功能。理解这八个函数就等于掌握了 SymPy 置换群算法内核的钥匙。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 SymPy 计算群论工具函数深度指南：combinatorics.util 模块与 BSGS 算法实战
SymPy 计算群论工具函数深度指南combinatorics.util 模块与 BSGS 算法实战【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy本文围绕 SymPy 的 combinatorics/util.py 模块展开系统讲解其内部为计算群论Computational Group Theory提供的八个核心工具函数从基base与强生成集strong generating set的组织到基本轨道、基本横截的计算再到置换筛选sifting与冗余生成元的剔除。读完本文你将理解这些函数在 Schreier-Sims 算法、陪集计算、正规闭包与对称/交错群判定等场景中的实际角色并能直接在 PermutationGroup 体系中复用它。一、模块定位BSGS 算法族的积木盒SymPy 的置换群功能核心位于 perm_groups.py而 combinatorics/util.py 则是支撑它的底层工具集。该模块的函数全部以下划线开头属于库内复用型基础设施但它们并非无人问津的内部细节——PermutationGroup的多个公开方法、以及张量规范型tensor canonical form算法 tensor_can.py都直接 import 并调用它们。从源码结构看这些函数共同服务于一套称为BSGS的核心数据结构。BSGS 是 Base 与 Strong Generating Set 的缩写其基本思想是基base一组点(b_1, ..., b_k)使得只有恒等置换同时固定它们基本稳定子basic stabilizersG^(i) G_{b_1,...,b_{i-1}}即逐点固定前i-1个基点的子群形成一条稳定子链G G^(1) ≥ G^(2) ≥ ... ≥ G^(k1) {e}强生成集strong generating set与基相容的一组生成元使得每个基本稳定子都由其中的相应子集生成。有了 BSGS群的阶、成员判定、陪集枚举等大量问题都可以转化为多项式时间的轨道计算。本文文档 util.rst 中列出的八个函数正是围绕 BSGS 的构造—分配—计算—精简—使用全流程设计的。二、快速上手安装与导入SymPy 是纯 Python 实现的计算机代数系统本模块仅依赖sympy.combinatorics.permutations与sympy.ntheory无第三方运行时依赖。可以从仓库根目录安装后使用pip install .然后即可导入模块并运行文中的示例 from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import _base_ordering S SymmetricGroup(4) S.schreier_sims() _base_ordering(S.base, S.degree) [0, 1, 2, 3]以下各节将逐一解析每个函数包括其参数、返回值、算法思想与源码级实现细节。三、核心函数逐一解析3.1_base_ordering(base, degree)为回溯搜索建立点序作用对点集{0, 1, ..., n-1}建立一种线性序使基点排在最前且按基的顺序排列。签名与返回接收base基与degree置换群的次数n返回列表base_ordering其中base_ordering[point]表示该点在序中的编号。算法核心见 util.py先把每个基点base[i]排在位置i再把不在基中的点按自然序依次接在后面。base_len len(base) ordering [0]*degree for i in range(base_len): ordering[base[i]] i current base_len for i in range(degree): if i not in base: ordering[i] current current 1 return ordering为什么要这样排序在回溯搜索backtrack search中需要定义点集上的关系≪使得基中靠前的点b_i排在靠后基点之前且任何基点都排在非基点之前。这样可以在陪集横截的构造中按base_ordering对元素排序、比较从而剪枝加速。此思想在 Holt、Eick、OBrien 的Handbook of Computational Group Theorypp. 108-132中有详细展开。实测用例来自 test_util.pybase [2, 4, 5] degree 7 assert _base_ordering(base, degree) [3, 4, 0, 5, 1, 2, 6]即基点 2、4、5 分别排在 0、1、2 位其余点 0、1、3、6 依次排在 3、4、5、6 位。调用方PermutationGroup.coset_transversal与_coset_representative见 perm_groups.py 与 L883用于按base_ordering[base[l]^x]排序横截元素、选取最小陪集代表元。3.2_check_cycles_alt_sym(perm)检测素数长循环作用判断置换中是否存在长度为素数p且满足n/2 p n-2的循环n为置换次数。这是PermutationGroup.is_alt_sym的辅助函数。理论基础群论与数论中的一个经典结果——若次数为n的传递群G含有一个长度为素数p、且n/2 p n-2的循环则G必为对称群或交错群见 perm_groups.py 的 Notes。实现要点util.py利用数组形式array_form沿j - af[j]追踪每个循环的长度只遍历前n//2个起点每个非平凡循环在到达n//2前必定已被遇到一旦发现满足条件的循环立即返回True否则返回False。示例源自文档 doctest from sympy.combinatorics.util import _check_cycles_alt_sym from sympy.combinatorics import Permutation a Permutation([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12]]) # n13 _check_cycles_alt_sym(a) False b Permutation([[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10]]) # n11 _check_cycles_alt_sym(b) True第一个例子中 11 长度循环满足11 13/2但11不小于n-2 11故不满足严格不等式p n-2返回False第二个例子中长度 7 的循环满足7/2 7 9且 7 为素数返回True。调用方_eval_is_alt_sym_monte_carloperm_groups.py在单侧蒙特卡洛测试中逐个检查随机抽样到的置换测试用例见 test_util.py其中perm1 [[0..6]]长度 7n10满足5 7 8判定为True。3.3_distribute_gens_by_base(base, gens)按基本稳定子分配生成元作用把一组生成元按固定前多少个基点分桶得到强生成集的稳定子链表示。返回长度为k len(base)的列表第i个元素是固定前i个基点的那些生成元故第 0 项等于gens本身若某级没有任何生成元固定相应基点则放入一个恒等置换占位保证每级非空。实现要点util.py对每个生成元gen从头扫描基点计算其最多连续固定多少个基点得到下标j随后把gen追加到stabs[0..j]中扫描结束后对剩余为空的下标填入恒等置换。示例源自文档 doctest from sympy.combinatorics.named_groups import DihedralGroup from sympy.combinatorics.util import _distribute_gens_by_base D DihedralGroup(3) D.schreier_sims() D.strong_gens [(0 1 2), (0 2), (1 2)] D.base [0, 1] _distribute_gens_by_base(D.base, D.strong_gens) [[(0 1 2), (0 2), (1 2)], [(1 2)]]调用方PermutationGroup.basic_stabilizers属性perm_groups.py、schreier_sims_incrementalL3707、normal_closureL2837以及张量规范型模块 tensor_can.py。此外 testutil.py 中的_verify_bsgs也用它来校验 BSGS 的正确性。3.4_handle_precomputed_bsgs(base, strong_gens, ...)补齐缺失的 BSGS 结构作用在已有基与强生成集的前提下按需补齐横截transversals、基本轨道basic orbits与按稳定子分配的强生成元避免重复计算。签名_handle_precomputed_bsgs(base, strong_gens, transversalsNone, basic_orbitsNone, strong_gens_distrNone)。返回三元组(transversals, basic_orbits, strong_gens_distr)。其补齐逻辑util.py是若strong_gens_distr为空调用_distribute_gens_by_base计算若transversals为空且basic_orbits也为空调用_orbits_transversals_from_bsgs一并计算若只有transversals为空则仅用transversals_onlyTrue计算横截若transversals已提供而basic_orbits为空则直接从横截字典的键提取轨道元素。示例源自文档 doctest对DihedralGroup(3)只传入basic_orbits D DihedralGroup(3) D.schreier_sims() _handle_precomputed_bsgs(D.base, D.strong_gens, ... basic_orbitsD.basic_orbits) ([{0: (2), 1: (0 1 2), 2: (0 2)}, {1: (2), 2: (1 2)}], [[0, 1, 2], [1, 2]], [[(0 1 2), (0 2), (1 2)], [(1 2)]])横截以字典列表形式给出第i个字典的键是基本轨道basic_orbits[i]中的点值是把base[i]送到该点的横截元素。调用方PermutationGroup.schreier_sims的内部路径_schreier_sims使用perm_groups.py它把用户传入的基、强生成元、横截、基本轨道统一整理为完整 BSGS 结构。测试见 test_util.py其中用AlternatingGroup(5)验证了横截元素确实把base[i]送到对应轨道点、且固定更靠前的基点并验证∏|basic_orbits[i]| |A|。3.5_orbits_transversals_from_bsgs(base, strong_gens_distr, ...)计算基本轨道与横截作用从基与已按稳定子分配的强生成元出发为每个基点计算基本轨道及其横截。签名_orbits_transversals_from_bsgs(base, strong_gens_distr, transversals_onlyFalse, slpFalse)。参数说明transversals_only默认False同时返回轨道与横截设为True时只返回横截列表slp默认False若为True额外返回一个字典列表记录每个横截元素相对strong_gens_distr[i]中生成元的生成子表示即生成元下标列表其乘积等于该横截元素这在需要记录群的元素表达式straight-line program时非常关键。实现要点util.py对每个基点base[i]调用perm_groups._orbit_transversal(degree, strong_gens_distr[i], base[i], pairsTrue, slpTrue)计算轨道横截对再转成字典。返回三种形态仅横截、(basic_orbits, transversals)、或(basic_orbits, transversals, slps)。示例源自文档 doctestSymmetricGroup(3) S SymmetricGroup(3) S.schreier_sims() strong_gens_distr _distribute_gens_by_base(S.base, S.strong_gens) (S.base, strong_gens_distr) ([0, 1], [[(0 1 2), (2)(0 1), (1 2)], [(1 2)]])调用方normal_closureperm_groups.py、_schreier_simsL3609此处传入slpTrue生成横截元素的生成子表示、coset_table相关路径L4167以及 tensor_can.py。测试 test_orbits_transversals_from_bsgs 验证了横截元素的正确性以及∏|basic_orbits[i]|等于群阶。3.6_remove_gens(base, strong_gens, ...)剔除冗余强生成元作用在保持相对于基仍是强生成集的前提下从强生成集中移除冗余生成元返回原集合的一个最小化子集。签名_remove_gens(base, strong_gens, basic_orbitsNone, strong_gens_distrNone)。若后两个参数未提供会先调用_distribute_gens_by_base与_orbit自动计算。算法思想util.py依据Handbook of Computational Group Theoryp.95从最高层稳定子向低层逆序遍历对每个生成元若它不固定下一层基点即不在更深的稳定子中则尝试把它从副本中删掉若删除后该层生成元生成的轨道仍覆盖basic_orbits[i]则确认删除——因为轨道未缩小说明它对该层是冗余的。示例源自文档 doctest并配合_verify_bsgs验证 from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import _remove_gens from sympy.combinatorics.testutil import _verify_bsgs S SymmetricGroup(15) base, strong_gens S.schreier_sims_incremental() new_gens _remove_gens(base, strong_gens) len(new_gens) 14 _verify_bsgs(S, base, new_gens) True测试覆盖test_remove_gens 分别对SymmetricGroup(10)、AlternatingGroup(7)、DihedralGroup(2)运行并断言_verify_bsgs通过说明精简后的集合仍是有效的 BSGS。3.7_strip(g, base, orbits, transversals)置换筛选sifting作用利用一个可能是部分的BSGS 结构尝试把置换g分解为标准形式。这一过程称为sifting筛选。签名_strip(g, base, orbits, transversals)其中orbits列表第i项是base[i]在某个隐含的基本稳定子下的轨道transversals与orbits对应的轨道横截字典列表。返回(h, level)二元组——h是筛选后剩下的置换level是筛选终止的层级。若成功h为恒等置换且level len(base) 1若失败某个轨道中找不到目标点或筛选结束不是恒等则返回中间态与失败层级。这两项信息对随机化 Schreier-Sims 算法至关重要失败的层级指明了需要在稳定子链的哪个位置补充新的强生成元见 perm_groups.py 的说明。实现要点util.py逐层处理对第i层取beta h(base[i])若beta base[i]说明已固定该点继续下一层若beta不在轨道中则筛选失败否则用横截元素u transversals[i][beta]左乘消除该层的贡献即h ← u⁻¹·h。示例源自文档 doctest from sympy.combinatorics import Permutation, SymmetricGroup from sympy.combinatorics.util import _strip S SymmetricGroup(5) S.schreier_sims() g Permutation([0, 2, 3, 1, 4]) _strip(g, S.base, S.basic_orbits, S.basic_transversals) ((4), 5)调用方normal_closureperm_groups.py用它判定共轭元素是否已落入当前生成子群schreier_sims_random用它筛选随机元素并据此修补稳定子链。测试 test_strip 用DihedralGroup(5)验证群内元素筛选后为恒等且层级为len(base)1群外元素要么保持自身、要么在中间层级失败。3.8_strong_gens_from_distr(strong_gens_distr)从分配结果还原强生成集作用把按基本稳定子分配的生成元列表压平为原始的强生成集。由于第 0 级稳定子即整个群G而任何固定了b_1的强生成元都同时出现在第 1 级中因此只需取第 0 级与第 1 级生成元的并集即可见 util.py 的实现。示例源自文档 doctest from sympy.combinatorics import SymmetricGroup from sympy.combinatorics.util import (_strong_gens_from_distr, ... _distribute_gens_by_base) S SymmetricGroup(3) S.schreier_sims() S.strong_gens [(0 1 2), (2)(0 1), (1 2)] strong_gens_distr _distribute_gens_by_base(S.base, S.strong_gens) _strong_gens_from_distr(strong_gens_distr) [(0 1 2), (2)(0 1), (1 2)]调用方PermutationGroup.baseswapperm_groups.py在交换基中相邻两点后用它从更新过的分配结构重建强生成集。测试 test_strong_gens_from_distr 验证了去重并集的正确性。3.9 补充_strip_af——数组形式的优化版筛选虽然不在文档 util.rst 的 autofunction 列表中但源码中还有其高性能版本_strip_af(h, base, orbits, transversals, j, slp[], slps{})util.py全程使用数组形式array form避免反复构造Permutation对象参数j记录h已固定前j1个基点筛选从j1层开始跳过已知不动的部分若slp非空同时累积生成子表示对横截元素的表示取逆并前插用于schreier_sims_incremental的slp_dictTrue模式返回约定不同若筛选结果为恒等直接返回(False, base_len1)h u时短路否则返回(h, level)或(h, level, slp)。它是schreier_sims_incremental主循环中检查 Schreier 生成元是否落入下一稳定子的关键步骤perm_groups.py。四、在 PermutationGroup 中的调用链一张功能地图结合上文各函数的调用方可以整理出这张工具函数 → 公开 API的功能地图工具函数主要调用方perm_groups.py服务场景_base_orderingcoset_transversal(L821)、_coset_representative(L883)陪集横截排序、陪集代表元选取_check_cycles_alt_sym_eval_is_alt_sym_monte_carlo(L1976)is_alt_sym单侧蒙特卡洛判定_distribute_gens_by_basebasic_stabilizers(L693)、schreier_sims_incremental(L3707)、normal_closure(L2837)稳定子链组织、BSGS 构造_handle_precomputed_bsgsschreier_sims路径 (L565)BSGS 结构补齐_orbits_transversals_from_bsgs_schreier_sims(L3609)、normal_closure(L2839)、coset_table(L4167)轨道与横截计算_remove_gens由用户直接调用配合_verify_bsgs强生成集精简_stripnormal_closure(L2850)、schreier_sims_random(L3908)元素分解、随机算法筛选_strip_afschreier_sims_incremental(L3748)确定性 Schreier-Sims 主循环_strong_gens_from_distrbaseswap(L612)基交换后重建强生成集此外_distribute_gens_by_base与_orbits_transversals_from_bsgs还被 tensor_can.py 用于张量规范型算法中的双陪集计算体现了这些工具跨越了纯群论与表示论应用两个领域。五、一致性验证_verify_bsgs与测试保障这些工具函数的正确性由 tests/test_util.py 中的九组测试全面覆盖重点包括轨道横截一致性对basic_orbits[i]中每个元素el断言transversals[i]el el且该横截元素固定所有更靠前的基点群阶恢复断言∏|basic_orbits[i]| G.order()这正是 BSGS 计算群阶的核心公式筛选判定群内元素筛选后得恒等、层级为len(base)1群外元素要么原样返回要么在中间层级失败精简有效性_remove_gens的输出必须继续通过 testutil.py 中_verify_bsgs的严格校验。六、数学背景与文献指引模块内多处注释引用了计算群论的经典教材Holt、Eick、OBrien 合著的Handbook of Computational Group Theory相关页码sifting 算法见 pp. 89-90增量式 Schreier-Sims 见 pp. 90-93_remove_gens见 p.95随机化版本见 pp. 97-98回溯搜索与点序思想见 pp. 108-132对称/交错群判定的素数循环准则见 pp. 81-82。读者若想深入理解这些工具的来龙去脉可以对照该教材研读相应章节再回到本模块源码中印证。总结sympy.combinatorics.util是 SymPy 计算群论引擎的积木盒——它本身不提供面向终端用户的 API却以清晰的分层结构支撑起 Schreier-Sims 算法、陪集计算、正规闭包与群类型判定等核心功能。理解这八个函数就等于掌握了 SymPy 置换群算法内核的钥匙。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考