SymPy 排列群测试工具库解析testutil 模块的校验器与朴素实现【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympysympy.combinatorics.testutil是 SymPy 排列群子系统sympy.combinatorics内部专用的测试工具模块它提供了一组以_开头的朴素实现naive implementation与校验函数用于独立验证PermutationGroup中centralizer、normal_closure、Schreier–Sims 算法BSGS等核心算法的正确性。阅读本文后你将理解这些工具的数学定义、调用方式与内部原理并掌握如何在 SymPy 中利用它们对排列群算法做交叉验证。模块定位为何需要一个专门的测试工具模块排列群算法如中心化子、正规闭包、base 与强生成集的实现通常依赖复杂的优化策略例如subgroup_search、Schreier–Sims 表示与 product replacement 随机算法见 perm_groups.py 中centralizer、normal_closure的实现注释。一旦优化逻辑出错很难直接判断结果是算法错误还是边界情况处理不当。testutil模块正是为此设计的它用直接从群论定义出发的暴力枚举重新计算同一结果再与被测算法比较。由于朴素实现路径简单、几乎不共享被测代码的逻辑两者结论一致时即可大幅提高置信度。模块内的测试还标注了verified by GAP见 test_testutil.py 的注释说明这些朴素函数的结果本身又经过了独立计算机代数系统 GAP 的交叉印证。从源码结构看模块位于 testutil.py主要依赖Permutation、PermutationGroup、_distribute_gens_by_base来自 util.py以及_af_commutes_with、_af_rmul、_af_invert等底层数组形式工具函数。排列列表的无序比较_cmp_perm_lists背景Permutation 为何不可哈希_cmp_perm_lists(first, second)该函数将两个排列列表作为集合比较忽略顺序。模块源码注释点明了它的存在理由由于排列的数组形式当前是 PythonlistPermutation不可哈希无法直接放入set因此需要把每个排列先转成tuple再做集合比较return {tuple(a) for a in first} {tuple(a) for a in second}使用示例 from sympy.combinatorics.permutations import Permutation from sympy.combinatorics.testutil import _cmp_perm_lists a Permutation([0, 2, 3, 4, 1]) b Permutation([1, 2, 0, 4, 3]) c Permutation([3, 4, 0, 1, 2]) ls1 [a, b, c] ls2 [b, c, a] _cmp_perm_lists(ls1, ls2) True由于generate_dimino等生成器产出的元素顺序并不保证一致而群运算结果如中心化子本质上是集合比较两个群是否相等时用_cmp_perm_lists是最稳妥的。测试 test_testutil.py 中将SymmetricGroup(4)的全部元素shuffle打乱后再比较验证了该函数的顺序无关性。朴素中心化子_naive_list_centralizer数学定义与算法给定群G与集合SS在G中的中心化子为所有与S每个元素可交换的元素集合C_G(S) { g ∈ G | gs sg, ∀ s ∈ S }_naive_list_centralizer(self, other, afFalse)的实现思路是用self.generate_dimino(afTrue)枚举群G的全部元素Dimino 算法见 perm_groups.py再对每个元素逐一检查其与other的生成元是否可交换判断依据是_af_commutes_with数组形式的交换性检测gens [x._array_form for x in other.generators] commutes_with_gens lambda x: all(_af_commutes_with(x, gen) for gen in gens)参数与返回self宿主群PermutationGroup其全部元素将被枚举other支持三种输入形态拥有generators属性即PermutationGroup拥有getitem属性排列列表内部先包装成PermutationGroup(other)拥有array_form属性单个排列同样包装为群af为True时返回数组形式list的元素列表否则返回Permutation对象列表。示例 from sympy.combinatorics.testutil import _naive_list_centralizer from sympy.combinatorics.named_groups import DihedralGroup D DihedralGroup(4) _naive_list_centralizer(D, D) [Permutation([0, 1, 2, 3]), Permutation([2, 3, 0, 1])]四阶二面体群的中心是其自身中的两个元素恒等元与 180° 旋转[2, 3, 0, 1]与群论结论一致。测试 test_testutil.py 还验证了SymmetricGroup(3)对AlternatingGroup(3)的朴素中心化子构成A3的子群。验证 base 与强生成集_verify_bsgs何为 BSGSSchreier–Sims 算法的输出是一对数据结构base点序列(b_1, ..., b_k)与相对于 base 的强生成集strong generating set。其核心性质是对每个基本稳定子群G^(i) G_{b_1,...,b_{i-1}}强生成集中恰好包含能生成它的那部分元素。_verify_bsgs(group, base, gens)不依赖 Schreier–Sims 的复杂推导而是直接用定义逐级验证。它调用_distribute_gens_by_base(base, gens)把生成元按固定前 i 个 base 点分组见 util.py第 0 组即全部生成元然后沿稳定子群链检查每一级current_stabilizer.order()是否等于该级候选群PermutationGroup(strong_gens_distr[i])的阶current_stabilizer group for i in range(len(base)): candidate PermutationGroup(strong_gens_distr[i]) if current_stabilizer.order() ! candidate.order(): return False current_stabilizer current_stabilizer.stabilizer(base[i]) if current_stabilizer.order() ! 1: return False return True最后一行的current_stabilizer.order() ! 1保证 base 确实完全固定了群即最终稳定子群为平凡群这是 base 定义的一部分。stabilizer(alpha)由 perm_groups.py 提供。示例与负例 from sympy.combinatorics.named_groups import AlternatingGroup from sympy.combinatorics.testutil import _verify_bsgs A AlternatingGroup(4) A.schreier_sims() _verify_bsgs(A, A.base, A.strong_gens) True测试 test_testutil.py 展示了它如何识别坏输入截断 basebase[:-1]后校验失败返回False改用普通生成元S.generators非强生成集也校验失败。这印证了 BSGS 中强生成集与任意生成元集的本质区别。中心化子交叉验证_verify_centralizer_verify_centralizer(group, arg, centrNone)该函数把被测的group.centralizer(arg)结果与_naive_list_centralizer的暴力结果做比较先计算或接收centr用generate_dimino(afTrue)枚举其全部元素再用_cmp_perm_lists与朴素列表比较if centr is None: centr group.centralizer(arg) centr_list list(centr.generate_dimino(afTrue)) centr_list_naive _naive_list_centralizer(group, arg, afTrue) return _cmp_perm_lists(centr_list, centr_list_naive)示例 from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) from sympy.combinatorics.perm_groups import PermutationGroup from sympy.combinatorics.permutations import Permutation from sympy.combinatorics.testutil import _verify_centralizer S SymmetricGroup(5) A AlternatingGroup(5) centr PermutationGroup([Permutation([0, 1, 2, 3, 4])]) _verify_centralizer(S, A, centr) True若传入centrNone函数会自动调用 perm_groups.py 中基于subgroup_search与 orbit/transversal 技巧的高效centralizer从而形成高效实现 ↔ 朴素实现的双向印证。注意PermutationGroup.centralizer允许arg的元素位于G之外只要G是全对称群的子群_verify_centralizer对此同样适用。正规闭包验证_verify_normal_closureS在G中的正规闭包是包含S的所有正规子群的交集等价于由所有共轭元素x^{-1}yxx遍历G的生成元y遍历子群生成元生成的群。_verify_normal_closure(group, arg, closureNone)朴素实现完全按照定义展开枚举group的全部元素收集每个生成元gen被el共轭后的结果用它们生成候选群再验证被测closure是它的子群for el in group.generate_dimino(): conjugates.update(gen ^ el for gen in subgr_gens) naive_closure PermutationGroup(list(conjugates)) return closure.is_subgroup(naive_closure)arg同样支持群 / 排列列表 / 单个排列三种输入。示例 from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) from sympy.combinatorics.testutil import _verify_normal_closure S SymmetricGroup(3) A AlternatingGroup(3) _verify_normal_closure(S, A, closureA) True测试 test_testutil.py 进一步验证S5中CyclicGroup(5)的正规闭包等于AlternatingGroup(5)因为 5-循环生成的子群在S5中的正规闭包正是A5与经典群论结论一致。被测的高效PermutationGroup.normal_closure位于 perm_groups.py其文档注明采用 product replacement 随机算法参数k控制一次邻接的共轭元素个数。同模块的扩展工具canonicalize_naive与graph_certificate除上述五个被文档自动收录.. autofunction::的函数外testutil.py 还包含两个相关朴素工具可用于理解本模块朴素对照的设计哲学canonicalize_naive(g, dummies, sym, *v)对由多种类型张量构成的张量做规范化canonicalization的朴素实现。它枚举对称群S与哑指标群D的全部元素对排列g逐一作用并收集结果若两个规范型在最后两个索引不同则判定张量为零否则返回数组形式的最小规范型。生产级版本是 tensor_can.py 中的canonicalize。graph_certificate(gr)为无向无环外线图计算不变量证书。它把图转化为对称张量顶点对应张量、边对应收缩指标再调用canonicalize得到规范型同构图将得到相同的证书。docstring 中gr1、gr2两个看似不同的 6 顶点图因为同构而得到相同证书c1 c2为True。这两个函数体现了testutil模块更广泛的用途用直白的暴力枚举为算法结果提供独立参照即使该算法本身位于其他模块如tensor_can。在测试套件中的实际使用与运行方式testutil的函数被组合进sympy.combinatorics.tests.test_testutil覆盖了上述全部五个接口统计见 test_testutil.py另在test_util.py、test_perm_groups.py中亦有引用。典型测试模式用schreier_sims()构造 BSGS再交给_verify_bsgs做正向 / 反向验证同时计算centralizer/normal_closure的高效与朴素版本用_cmp_perm_lists或is_subgroup比对在测试注释中标注 verified by GAP将朴素结果锚定到独立系统的输出上。在仓库根目录下可以运行相关测试测试文件位于 sympy/combinatorics/tests/python -m pytest sympy/combinatorics/tests/test_testutil.py也可在交互式 Python 会话中直接导入使用from sympy.combinatorics.named_groups import SymmetricGroup, AlternatingGroup from sympy.combinatorics.testutil import _verify_bsgs, _verify_centralizer, _verify_normal_closure S SymmetricGroup(5) S.schreier_sims() _verify_bsgs(S, S.base, S.strong_gens) # True _verify_centralizer(S, AlternatingGroup(5)) # True _verify_normal_closure(S, AlternatingGroup(5)) # True小结sympy.combinatorics.testutil以朴素即真理为设计原则通过五组核心函数——_cmp_perm_lists集合级比较、_naive_list_centralizer暴力中心化子、_verify_bsgsBSGS 定义级验证、_verify_centralizer与_verify_normal_closure高效实现 ↔ 朴素实现交叉验证——为排列群算法提供了不共享被测逻辑的独立参照系。对于希望理解 SymPy 排列群模块内部机制或为其贡献新算法的开发者这些函数既是现成的验证脚手架也是理解centralizer、normal_closure、Schreier–Sims 等算法语义的绝佳入口相关定义与示例可进一步查阅 testutil.rst 与 test_testutil.py。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考