SymPy Prufer 序列详解sympy.combinatorics.prufer.Prufer完整使用指南【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy本文是 SymPy 组合数学子库sympy/combinatorics中 Prufer 序列模块的深度技术指南。Prufer 序列是标记树labeled tree与整数序列之间的一一对应其长度为 n−2也是 Cayley 公式n 个顶点的标记树共有 n^(n−2) 棵的经典证明工具。阅读本文后你将掌握Prufer类的全部属性与方法能够熟练完成「树 ↔ Prufer 序列」的双向转换、序列排名rank/unrank以及按字典序遍历所有标记树。1. Prufer 对应算法背景与模块定位Prufer 对应Prufer correspondence是一个描述标记树与Prufer 序列之间双射关系的算法。其核心事实有三点见 prufer.py 中的类文档每个标记树的 Prufer 序列在顶点标签重命名意义上的同构下是唯一的序列的长度为 n − 2其中 n 是树的顶点数反过来任意一个长度为 n − 2、元素取自 {0, 1, …, n−1} 的序列都唯一对应一棵标记树。这一对应最早由 Heinz Prufer 提出用于给出 Cayley 公式的证明由于每个长度为 n−2、每项有 n 种取值的序列都对应一棵唯一的标记树因此 n 个顶点的标记树总数为 n^(n−2)。在 SymPy 中该算法被封装为sympy.combinatorics.prufer.Prufer类并从 组合数学包的公开入口 导出from sympy.combinatorics.prufer import Prufer与Permutation、Subset、GrayCode等类并列在组合学工具集中见 combinatorics/index.rst。本模块的 API 结构如下类别成员属性propertyprufer_repr、tree_repr、nodes、rank、size静态方法to_prufer(tree, n)、to_tree(prufer)、edges(*runs)实例/类方法prufer_rank()、unrank(rank, n)、next(delta1)、prev(delta1)2. 构造Prufer对象两种输入形态Prufer对象可以通过边列表或Prufer 序列两种方式构造构造逻辑见 prufer.py 中的__new__。2.1 由边列表构造并自动推导节点数 from sympy.combinatorics.prufer import Prufer a Prufer([[0, 1], [0, 2], [0, 3]]) a.prufer_repr [0, 0]当只给出边列表而未显式给出节点数 n 时构造器会从边中收集所有出现过的节点标签取max(nodes) 1作为节点数并校验标签是否连续完整。若中间缺号会抛出ValueError Prufer([[1, 2], [3, 4]]) # 节点 0 缺失 Traceback (most recent call last): ... ValueError: Node 0 is missing. Prufer([[2, 3], [3, 4]]) # 节点 0、1 缺失 ValueError: Nodes [0, 1] are missing.对应测试见 test_prufer.py。2.2 显式指定节点数跳过校验如果显式传入第二个参数 n则不再校验节点连续性直接假定节点 0 到 n−1 全部存在 Prufer([[0, 1], [0, 2], [0, 3]], 4) Prufer([[0, 1], [0, 2], [0, 3]], 4)节点数是可选参数两种写法等价 Prufer([[0, 1], [0, 2], [0, 3], [0, 4]], 5).nodes 5 Prufer([[0, 1], [0, 2], [0, 3], [0, 4]]).nodes 5见 test_prufer.py。2.3 由 Prufer 序列构造直接传入长度为 n−2 的序列此时节点数自动为len(序列) 2 b Prufer([1, 3]) b.tree_repr [[0, 1], [1, 3], [2, 3]]2.4 其他构造细节接受元组、集合等可迭代输入内部会转换为「列表的列表」例如Prufer((0, 1), ...)形式的边元组与Prufer(set(...))都可用测试见 test_prufer.py空边列表如Prufer([[]])会抛出ValueError: Prufer expects at least one edge in the tree.见 prufer.py。3. 属性五种只读视图Prufer对象内部通过_prufer_repr、_tree_repr、_nodes、_rank四个私有字段做懒缓存属性访问时按需计算并缓存见 prufer.py。3.1prufer_repr当前对象的 Prufer 序列返回该对象对应的 Prufer 序列。其生成算法为反复删除编号最大的叶子节点记录它所连接的节点直到只剩两个顶点记录下来的节点列表即为 Prufer 序列见 prufer.py。 Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).prufer_repr [3, 3, 3, 4]返回的是内部序列的拷贝self._prufer_repr[:]因此外部修改返回值不会污染对象内部状态——test_prufer_repr_aliasing测试专门验证了这一点见 test_prufer.py。3.2tree_repr边列表形式的树表示返回树以边列表形式。如果对象由边构造则原样返回如果对象由序列构造则调用to_tree恢复出树 Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).tree_repr [[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]] Prufer([1, 0, 0]).tree_repr [[1, 2], [0, 1], [0, 3], [0, 4]]同样返回拷贝[edge[:] for edge in self._tree_repr]外部对边内部列表的修改不会影响对象见test_tree_repr_aliasingtest_prufer.py。3.3nodes树的节点数 Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).nodes 6 Prufer([1, 0, 0]).nodes 5注意nodes与序列长度满足恒等式nodes len(prufer_repr) 2。3.4rankPrufer 序列的排名将 Prufer 序列视为「n 进制数」每个位置取值 0..n−1从高位到低位加权求和得到排名范围是 0 到 n^(n−2)−1 p Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]) p.rank 778 p.next(1).rank 779 p.prev().rank 777实现与示例见 prufer.py 与prufer_rank方法。3.5size当前节点数下可能的树的总数即 n 个顶点标记树的总数 n^(n−2)Cayley 公式的直接体现 Prufer([0]*4).size Prufer([6]*4).size 1296 True对 n 6 的树总数为 6^(6−2) 1296。实现上size通过prev(rank).prev().rank 1计算见 prufer.py。4. 静态方法核心双向转换算法4.1to_prufer(tree, n)树 → 序列给定边列表形式的树与节点数 n返回其 Prufer 序列。算法步骤如下见 prufer.py遍历所有边统计每个节点的度数d[x]重复 n−2 次找出编号最小的叶子度数为 1 的节点x找到 x 所连接的节点 y将 y 记入结果L将 x、y 的度数各减 1度数归零的节点从字典中移除从树中删除边 (x, y)。 a Prufer([[0, 1], [0, 2], [0, 3]]) a.prufer_repr [0, 0] Prufer.to_prufer([[0, 1], [0, 2], [0, 3]], 4) [0, 0]注意to_prufer是静态方法可以直接以Prufer.to_prufer(tree, n)形式调用。4.2to_tree(prufer)序列 → 树给定 Prufer 序列恢复出树的边列表这是to_prufer的逆过程。算法思路见 prufer.py节点数 n len(prufer) 2初始化度数字典每个节点默认度数 1序列中每出现一次 v 则d[v]加 1即「出现次数 1」依次扫描序列中的每个值 i找到编号最小的度数等于 1 的节点 j把边 (i, j)排序后加入树i、j 的度数各减 1最后把剩余两个度数为 1 的节点连成最后一条边。 a Prufer([0, 2], 4) a.tree_repr [[0, 1], [0, 2], [2, 3]] Prufer.to_tree([0, 2]) [[0, 1], [0, 2], [2, 3]]4.3edges(*runs)从路径片段构造边集这是一个非常实用的辅助工具给定若干条「路径片段」runs提取其中所有唯一的无向边并返回 (边列表, 节点数) 二元组。所有节点编号会被平移使得最小节点为 0见 prufer.py。 Prufer.edges([1, 2, 3], [2, 4, 5]) # 形如字母 T 的树 ([[0, 1], [1, 2], [1, 3], [3, 4]], 5)重复的边会被自动去重片段之间的公共顶点会自然合并成树 Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) # 形如字母 K 的树 ([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)edges的约束与行为节点标签范围不必从 0 开始但最小到最大之间的所有整数节点必须出现否则抛ValueError。例如Prufer.edges([1, 2], [5, 6])因中间节点缺失而报错见 test_prufer.py它不校验输入是否真的构成树——比如Prufer.edges([1, 3], [3, 4])表示一条「断裂」的路径节点 2 缺失edges同样会因节点缺失抛错见 test_prufer.py结果中的节点编号会平移至从 0 开始返回值(edges, n)可以直接拆包传给Prufer构造器。一个组合用法示例 Prufer(*Prufer.edges([1, 2], [3, 4])).prufer_repr [1, 3]对应测试见 test_prufer.py。5. 排名系统rank、unrank、next、prevPrufer 序列可以按「n 进制整数」排序SymPy 提供了完整的排名与反排名工具可用于系统地枚举/遍历所有 n 顶点标记树。5.1prufer_rank()计算序列排名把序列视为 n 进制数rank Σ prufer_repr[i] * n^i低位为序列末位见 prufer.py a Prufer([[0, 1], [0, 2], [0, 3]]) a.prufer_rank() 05.2unrank(rank, n)由排名反查序列类方法unrank(rank, n)是prufer_rank的逆运算通过反复取模与整除恢复出 n−2 位的 n 进制表示见 prufer.py Prufer.unrank(0, 4) Prufer([0, 0])5.3next(delta1)/prev(delta1)按排名顺序步进next(delta1)返回排名加 delta的序列所对应的对象见 prufer.py a Prufer([[0, 1], [0, 2], [0, 3]]) b a.next(1) # 等价于 a.next() b.tree_repr [[0, 2], [0, 1], [1, 3]] b.rank 1prev(delta1)返回排名减 delta的序列所对应的对象见 prufer.py a Prufer([[0, 1], [1, 2], [2, 3], [1, 4]]) a.rank 36 b a.prev() b Prufer([1, 2, 0]) b.rank 35两者内部均通过Prufer.unrank(self.rank ± delta, self.nodes)实现因此步进是严格按 n 进制整数顺序进行的。这一套 rank/unrank/next/prev/size 工具共同构成了对全部标记树的可枚举遍历框架相关See Also交叉引用见各方法文档。6. 双向转换验证测试用例中的证据仓库的单元测试 test_prufer.py 完整验证了上述 API 的正确性其中最有说服力的是test_round_triptest_prufer.py它构造了从 2 节点到 8 节点共 18 组树逐一验证Prufer.edges(*t)从路径片段得到边集与节点数Prufer(e, n).prufer_repr与预期序列一致由序列Prufer(b).tree_repr能还原出原来的树tree → prufer → tree闭环Prufer.unrank(t.rank, n).prufer_repr brank/unrank 闭环。例如对于 8 节点的树Prufer.edges([6, 2, 1, 4], [1, 3, 5, 8], [3, 7])对应序列[1, 2, 1, 3, 3, 5]且可完整往返。这一测试同时印证了上一节edges与构造器、rank/unrank之间的协作关系。此外combinatoric_cheatsheet.tex 将Prufer的全部方法与属性收录为速查表可作为 API 概览的快速参考。7. 完整实战示例从树到序列再到排名遍历综合以上知识一个端到端的使用流程如下 from sympy.combinatorics.prufer import Prufer # 1. 用路径片段构建一棵树 edges, n Prufer.edges([1, 2, 3], [2, 4, 5]) edges, n ([[0, 1], [1, 2], [1, 3], [3, 4]], 5) # 2. 构造对象并查看两种表示 t Prufer(edges, n) t.tree_repr [[0, 1], [1, 2], [1, 3], [3, 4]] t.prufer_repr [1, 2, 1] t.nodes 5 # 3. 排名与遍历 t.rank 15 t.next().tree_repr # 排名 1 对应的下一棵树 [[0, 1], [1, 2], [2, 3], [3, 4]] t.prev().tree_repr # 排名 -1 对应的上一棵树 [[0, 1], [0, 2], [1, 3], [3, 4]] # 4. 总树数Cayley 公式5^(5-2) 125 t.size 1258. 适用前提与边界说明节点标签约定为整数 0 到 n−1从边列表构造时若不显式给 n会自动校验标签连续性edges则负责把任意整数标签平移归一到从 0 开始to_prufer/to_tree的语义针对标记树若输入并非合法树如含环、缺节点会抛出ValueError或产生未定义结果使用前建议先用edges等工具规整输入rank/size均以「n 个顶点」为参数空间同一序列在不同 n 下排名不同调用next/prev/unrank时需保持节点数一致本模块不依赖任何外部计算库纯粹基于 Python 内建容器collections.defaultdict实现适合作为组合枚举、图论教学与算法验证的轻量工具。【免费下载链接】sympyA computer algebra system written in pure Python项目地址: https://gitcode.com/GitHub_Trending/sy/sympy创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考