Prufer 序列¶

class sympy.combinatorics.prufer.Prufer(*args, **kw_args)[源代码][源代码]¶

Prufer 对应关系是一种描述标记树与 Prufer 码之间双射关系的算法。一个标记树的 Prufer 码在同构意义下是唯一的，并且长度为 n - 2。

Prufer 序列最早由 Heinz Prufer 使用，用于证明 Cayley 公式。

属性:

args: 返回 ‘self’ 的参数元组。
assumptions0: 返回对象 \(type\) 假设。
canonical_variables: 返回一个字典，将 self.bound_symbols 中定义的任何变量映射到与表达式中任何自由符号不冲突的符号。
expr_free_symbols
free_symbols: 从自身的原子中返回那些自由符号。
func: 表达式中的顶级函数。
is_algebraic
is_antihermitian
is_commutative
is_comparable: 如果 self 可以计算为一个具有精度的实数（或已经是一个实数），则返回 True，否则返回 False。
is_complex
is_composite
is_even
is_extended_negative
is_extended_nonnegative
is_extended_nonpositive
is_extended_nonzero
is_extended_positive
is_extended_real
is_finite
is_hermitian
is_imaginary
is_infinite
is_integer
is_irrational
is_negative
is_noninteger
is_nonnegative
is_nonpositive
is_nonzero
is_odd
is_polar
is_positive
is_prime
is_rational
is_real
is_transcendental
is_zero
nodes: 返回树中节点的数量。
prufer_repr: 返回 Prufer 对象的 Prufer 序列。
rank: 返回 Prufer 序列的秩。
size: 返回此 Prufer 对象的可能树的数量。
tree_repr: 返回 Prufer 对象的树表示。

方法

`as_content_primitive`([radical, clear])	一个存根，允许在计算表达式的内容和基本组件时跳过基本参数（如元组）。
`as_dummy`()	返回表达式，其中任何具有结构绑定符号的对象都被替换为在其出现的对象中唯一的规范符号，并且仅对交换性具有默认假设为True。
`atoms`(*types)	返回构成当前对象的原子。
`class_key`()	类的好顺序。
`compare`(other)	如果对象在规范意义上小于、等于或大于其他对象，则返回 -1、0、1。
`count`(query)	计算匹配的子表达式的数量。
`count_ops`([visual])	用于返回操作计数的 count_ops 的包装器。
`doit`(**hints)	评估默认情况下不评估的对象，如极限、积分、求和和乘积。
`dummy_eq`(other[, symbol])	比较两个表达式并处理哑符号。
`edges`(*runs)	返回一个边列表和从给定运行中连接整数标记树中节点的节点数。
`find`(query[, group])	查找所有匹配查询的子表达式。
`fromiter`(args, **assumptions)	从可迭代对象创建一个新对象。
`has`(*patterns)	测试是否有任何子表达式匹配任何模式。
`has_free`(*patterns)	如果 self 包含对象 `x` 作为自由表达式，则返回 True，否则返回 False。
`has_xfree`(s)	如果 self 有 s 中的任何一个模式作为自由参数，则返回 True，否则返回 False。
`is_same`(b[, approx])	如果 a 和 b 结构相同则返回 True，否则返回 False。
`match`(pattern[, old])	模式匹配。
`matches`(expr[, repl_dict, old])	用于 match() 的辅助方法，用于在 self 中的通配符符号与 expr 中的表达式之间寻找匹配。
`next`([delta])	生成当前序列之外的 delta 的 Prufer 序列。
`prev`([delta])	生成当前序列之前的 -delta 的 Prufer 序列。
`prufer_rank`()	计算Prufer序列的秩。
`rcall`(*args)	通过表达式树递归应用于参数。
`refine`([assumption])	请参阅 sympy.assumptions 中的 refine 函数。
`replace`(query, value[, map, simultaneous, exact])	将 `self` 中匹配的子表达式替换为 `value`。
`rewrite`(*args[, deep])	使用定义的规则重写 self。
`simplify`(**kwargs)	请参阅 sympy.simplify 中的 simplify 函数。
`sort_key`([order])	返回一个排序键。
`subs`(args, *kwargs)	在简化参数后，在表达式中用新内容替换旧内容。
`to_prufer`(tree, n)	返回给定树的Prufer序列，该树以边列表的形式给出，其中 `n` 是树中节点的数量。
`to_tree`(prufer)	返回给定 Prufer 序列的树（作为边的列表）。
`unrank`(rank, n)	找到未排序的Prufer序列。
`xreplace`(rule)	替换表达式中对象的出现。

复制
could_extract_minus_sign
is_hypergeometric

参考文献

[1]

https://mathworld.wolfram.com/LabeledTree.html

static edges(*runs)[源代码][源代码]¶

返回一个边列表和从给定运行中连接整数标记树中节点的节点数。

所有节点编号将被调整，使得最小的节点编号为0。如果在运行中重复边，这不是问题；只返回唯一的边。对节点标签的范围没有假设，但从最小到最大的所有节点都必须存在。

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer.edges([1, 2, 3], [2, 4, 5]) # a T
([[0, 1], [1, 2], [1, 3], [3, 4]], 5)

重复的边被移除：

>>> Prufer.edges([0, 1, 2, 3], [1, 4, 5], [1, 4, 6]) # a K
([[0, 1], [1, 2], [1, 4], [2, 3], [4, 5], [4, 6]], 7)

next(delta=1)[源代码][源代码]¶

生成当前序列之外的 delta 的 Prufer 序列。

参见

prufer_rank, rank, prev, size

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> 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
1

property nodes¶

返回树中节点的数量。

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).nodes
6
>>> Prufer([1, 0, 0]).nodes
5

prev(delta=1)[源代码][源代码]¶

生成当前序列之前的 -delta 的 Prufer 序列。

参见

prufer_rank, rank, next, size

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> 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_rank()[源代码][源代码]¶

计算Prufer序列的秩。

参见

rank, next, prev, size

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> a = Prufer([[0, 1], [0, 2], [0, 3]])
>>> a.prufer_rank()
0

property prufer_repr¶

返回 Prufer 对象的 Prufer 序列。

这个序列是通过移除编号最高的顶点，记录它所连接的节点，并继续这一过程，直到只剩下两个顶点为止。Prufer 序列就是记录的节点列表。

参见

to_prufer

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]]).prufer_repr
[3, 3, 3, 4]
>>> Prufer([1, 0, 0]).prufer_repr
[1, 0, 0]

property rank¶

返回 Prufer 序列的秩。

参见

prufer_rank, next, prev, size

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> p = Prufer([[0, 3], [1, 3], [2, 3], [3, 4], [4, 5]])
>>> p.rank
778
>>> p.next(1).rank
779
>>> p.prev().rank
777

property size¶

返回此 Prufer 对象的可能树的数量。

参见

prufer_rank, rank, next, prev

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer([0]*4).size == Prufer([6]*4).size == 1296
True

static to_prufer(tree, n)[源代码][源代码]¶

返回给定树的Prufer序列，该树以边列表的形式给出，其中 n 是树中节点的数量。

参见

prufer_repr: 返回一个 Prufer 对象的 Prufer 序列。

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> 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]

static to_tree(prufer)[源代码][源代码]¶

返回给定 Prufer 序列的树（作为边的列表）。

参见

tree_repr: 返回 Prufer 对象的树表示。

参考文献

[1]

https://hamberg.no/erlend/posts/2010-11-06-prufer-sequence-compact-tree-representation.html

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> 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]]

property tree_repr¶

返回 Prufer 对象的树表示。

参见

to_tree

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> 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]]

classmethod unrank(rank, n)[源代码][源代码]¶

找到未排序的Prufer序列。

示例

>>> from sympy.combinatorics.prufer import Prufer
>>> Prufer.unrank(0, 4)
Prufer([0, 0])