SymPy 排列群测试工具库解析：testutil 模块的校验器与朴素实现-平芜编程栈

SymPy 排列群测试工具库解析：testutil 模块的校验器与朴素实现

【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy

sympy.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)

该函数将两个排列列表作为集合比较（忽略顺序）。模块源码注释点明了它的存在理由：由于排列的数组形式当前是 Pythonlist，Permutation不可哈希，无法直接放入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与集合S，S在G中的中心化子为所有与S每个元素可交换的元素集合：

C_G(S) = { g ∈ G | gs = sg, ∀ s ∈ S }

_naive_list_centralizer(self, other, af=False)的实现思路是：用self.generate_dimino(af=True)枚举群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`

何为 BSGS

Schreier–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 展示了它如何识别坏输入：

截断 base（base[:-1]）后校验失败（返回False）；
改用普通生成元S.generators（非强生成集）也校验失败。

这印证了 BSGS 中"强生成集"与"任意生成元集"的本质区别。

中心化子交叉验证：`_verify_centralizer`

_verify_centralizer(group, arg, centr=None)

该函数把被测的group.centralizer(arg)结果与_naive_list_centralizer的暴力结果做比较：先计算（或接收）centr，用generate_dimino(af=True)枚举其全部元素，再用_cmp_perm_lists与朴素列表比较：

if centr is None: centr = group.centralizer(arg) centr_list = list(centr.generate_dimino(af=True)) centr_list_naive = _naive_list_centralizer(group, arg, af=True) 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

若传入centr=None，函数会自动调用 perm_groups.py 中基于subgroup_search与 orbit/transversal 技巧的高效centralizer，从而形成"高效实现 ↔ 朴素实现"的双向印证。注意：PermutationGroup.centralizer允许arg的元素位于G之外（只要G是全对称群的子群），_verify_centralizer对此同样适用。

正规闭包验证：`_verify_normal_closure`

S在G中的正规闭包是包含S的所有正规子群的交集，等价于由所有共轭元素x^{-1}yx（x遍历G的生成元，y遍历子群生成元）生成的群。

_verify_normal_closure(group, arg, closure=None)

朴素实现完全按照定义展开：枚举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, closure=A) 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_bsgs（BSGS 定义级验证）、_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），仅供参考

SymPy 排列群测试工具库解析：testutil 模块的校验器与朴素实现