枚举

此模块包含用于枚举和计数多重集分区的函数和类。

sympy.utilities.enumerative.multiset_partitions_taocp(multiplicities)

枚举多重集的分区。

参数:

多重性

多重集的组成部分的整数重数的列表。

Yields:

状态

编码特定分区的内部数据结构。此输出通常由访问者函数处理，该函数将此数据结构中的信息与组件本身结合，以生成实际的分区。

除非他们希望创建自己的访问者函数，用户将很少需要查看此数据结构内部。但作为参考，它是一个包含以下组件的3元素列表：

f

是一个帧数组，用于将 pstack 分成多个部分。

lpart

指向最顶部的基部。

pstack

是一个 PartComponent 对象的数组。

state 输出提供了对枚举函数内部数据结构的窥视。客户端应将其视为只读；任何对数据结构的修改都将导致不可预测（且几乎肯定是错误的）结果。此外，state 的组件在每次迭代中都会就地修改。因此，访问者必须在每次循环迭代中被调用。累积 state 实例并在之后处理它们将不起作用。

参见

sympy.utilities.iterables.multiset_partitions

接受一个多重集作为输入，并直接生成多重集的分区。它分派给多个函数，包括这个函数，用于实现。大多数用户会发现它比使用 multiset_partitions_taocp 更方便。

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import multiset_partitions_taocp
>>> # variables components and multiplicities represent the multiset 'abb'
>>> components = 'ab'
>>> multiplicities = [1, 2]
>>> states = multiset_partitions_taocp(multiplicities)
>>> list(list_visitor(state, components) for state in states)
[[['a', 'b', 'b']],
[['a', 'b'], ['b']],
[['a'], ['b', 'b']],
[['a'], ['b'], ['b']]]

sympy.utilities.enumerative.factoring_visitor(state, primes)

使用 multiset_partitions_taocp 来枚举一个数可以表示为因子乘积的方式。对于这种用法，一个数的质因数的指数是分区枚举器的参数，而相应的质因数在这里输入。

示例

要枚举一个数的因式分解，我们可以将分区的元素视为质因数，而将它们的乘数视为指数。

>>> from sympy.utilities.enumerative import factoring_visitor
>>> from sympy.utilities.enumerative import multiset_partitions_taocp
>>> from sympy import factorint
>>> primes, multiplicities = zip(*factorint(24).items())
>>> primes
(2, 3)
>>> multiplicities
(3, 1)
>>> states = multiset_partitions_taocp(multiplicities)
>>> list(factoring_visitor(state, primes) for state in states)
[[24], [8, 3], [12, 2], [4, 6], [4, 2, 3], [6, 2, 2], [2, 2, 2, 3]]

sympy.utilities.enumerative.list_visitor(state, components)

返回一个列表的列表来表示分区。

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import multiset_partitions_taocp
>>> states = multiset_partitions_taocp([1, 2, 1])
>>> s = next(states)
>>> list_visitor(s, 'abc')  # for multiset 'a b b c'
[['a', 'b', 'b', 'c']]
>>> s = next(states)
>>> list_visitor(s, [1, 2, 3])  # for multiset '1 2 2 3
[[1, 2, 2], [3]]

函数 multiset_partitions_taocp 的方法被类 MultisetPartitionTraverser 扩展和泛化。

class sympy.utilities.enumerative.MultisetPartitionTraverser

具有 enumerate 和 count 多重集分区的 \(方法\)。

这实现了Knuth算法7.1.2.5M [Rba910898fc1a-AOCP]_的改进和扩展版本。

此类中的枚举方法是生成器，并返回可由用于 multiset_partitions_taocp 输出的相同访问者函数解释的数据结构。

方法

count_partitions(multiplicities)	返回一个多重集的分区数，其组成部分的重复次数在 multiplicities 中给出。
enum_all(multiplicities)	枚举多重集的分区。
enum_large(multiplicities, lb)	列举一个多重集的分区，其中 lb < num(parts)
enum_range(multiplicities, lb, ub)	列举一个多重集合的分区，其中 lb < num(parts) <= ub。
enum_small(multiplicities, ub)	枚举不超过 ub 部分的多元集分区。

参见

multiset_partitions_taocp

sympy.utilities.iterables.multiset_partitions

参考文献

[AOCP]

算法 7.1.2.5M 在 Donald Knuth 所著的《计算机程序设计艺术》第四卷 A 部分，组合算法，第一部分中。

[Factorisatio]

关于Oppenheim的“Factorisatio Numerorum”问题 E. R. Canfield, Paul Erdos, Carl Pomerance, 《数论杂志》, 第17卷, 第1期. 1983年8月. 参见第7节，描述了一个类似于Knuth的算法。

[Yorgey]

生成多集分区，Brent Yorgey，The Monad.Reader，第8期，2007年9月。

示例

>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> m.count_partitions([4,4,4,2])
127750
>>> m.count_partitions([3,3,3])
686

count_partitions(

multiplicities,

)

返回一个多重集的分区数，其组成部分的重复次数在 multiplicities 中给出。

对于较大的计数，此方法比调用其中一个枚举器并计算结果要快得多。使用动态规划来减少实际探索的节点数量。用于加速计数过程的字典存储在 MultisetPartitionTraverser 对象中，并在调用之间持久化。如果用户不期望为任何其他多重集调用 count_partitions，则应清除对象以节省内存。另一方面，从一个计数运行中构建的缓存可以显著加快后续调用 count_partitions 的速度，因此不清除对象可能是有利的。

注释

如果观察 Knuth 的算法 M [AOCP] 的工作原理，可以将其视为对一个部分二叉树的遍历。一个部分最多有两个子节点，左子节点由展开操作产生，右子节点由递减操作产生。多重集分区的普通枚举是对这棵树的中序遍历，分区对应于从根到叶子的路径。从路径到分区的映射有点复杂，因为分区只包含那些作为叶子或展开链接父节点的部分，而不包含那些作为递减链接父节点的部分。

为了计数目的，只需计算叶子节点即可，这可以通过递归的中序遍历来完成。以特定部分为根的子树的叶子节点数量仅取决于该部分本身，因此记忆化有可能显著加快计数速度。

这种方法遵循一种计算方法，类似于假设的记忆化递归函数，但有两个不同之处：

1. 这种方法是迭代的，借鉴了其他枚举的结构，并维护了一个正在计数的部件的显式堆栈。（可能存在一些多重集可以通过这种实现方式合理快速地计数，但如果使用递归实现，它们可能会超出Python的默认递归限制。）

2. 不直接使用部分数据结构，而是构建一个更紧凑的键。这节省了空间，但更重要的是将一些原本在物理键下保持分离的部分合并在一起。

与枚举函数不同，目前没有 _range 版本的 count_partitions。如果有人想挑战自己的大脑，通过使用计数的直方图而不是单个计数进行记忆化，并结合这些直方图，应该是可以构建一个的。

示例

>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> m.count_partitions([9,8,2])
288716
>>> m.count_partitions([2,2])
9
>>> del m

enum_all(

multiplicities,

)

枚举多重集的分区。

参见

multiset_partitions_taocp

这种方法提供了相同的结果，但速度大约快两倍。因此，enum_all 主要用于测试。另请参阅函数以讨论状态和访问者。

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> states = m.enum_all([2,2])
>>> list(list_visitor(state, 'ab') for state in states)
[[['a', 'a', 'b', 'b']],
[['a', 'a', 'b'], ['b']],
[['a', 'a'], ['b', 'b']],
[['a', 'a'], ['b'], ['b']],
[['a', 'b', 'b'], ['a']],
[['a', 'b'], ['a', 'b']],
[['a', 'b'], ['a'], ['b']],
[['a'], ['a'], ['b', 'b']],
[['a'], ['a'], ['b'], ['b']]]

enum_large(

multiplicities,

lb,

)

列举一个多重集的分区，其中 lb < num(parts)

等价于 enum_range(multiplicities, lb, sum(multiplicities))

参数:

多重性

多重集的组成部分的多重性列表。

lb

分区中的部分数量必须大于此下限。

参见

enum_all, enum_small, enum_range

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> states = m.enum_large([2,2], 2)
>>> list(list_visitor(state, 'ab') for state in states)
[[['a', 'a'], ['b'], ['b']],
[['a', 'b'], ['a'], ['b']],
[['a'], ['a'], ['b', 'b']],
[['a'], ['a'], ['b'], ['b']]]

enum_range(

multiplicities,

lb,

ub,

)

列举一个多重集合的分区，其中 lb < num(parts) <= ub。

特别是，如果需要恰好有 k 部分的划分，请使用 (multiplicities, k - 1, k) 调用。此方法概括了 enum_all、enum_small 和 enum_large。

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> states = m.enum_range([2,2], 1, 2)
>>> list(list_visitor(state, 'ab') for state in states)
[[['a', 'a', 'b'], ['b']],
[['a', 'a'], ['b', 'b']],
[['a', 'b', 'b'], ['a']],
[['a', 'b'], ['a', 'b']]]

enum_small(

multiplicities,

ub,

)

枚举不超过 ub 部分的多元集分区。

等同于 enum_range(multiplicities, 0, ub)

参数:

多重性

多重集的组成部分的多重性列表。

ub

最大部件数

参见

enum_all, enum_large, enum_range

示例

>>> from sympy.utilities.enumerative import list_visitor
>>> from sympy.utilities.enumerative import MultisetPartitionTraverser
>>> m = MultisetPartitionTraverser()
>>> states = m.enum_small([2,2], 2)
>>> list(list_visitor(state, 'ab') for state in states)
[[['a', 'a', 'b', 'b']],
[['a', 'a', 'b'], ['b']],
[['a', 'a'], ['b', 'b']],
[['a', 'b', 'b'], ['a']],
[['a', 'b'], ['a', 'b']]]

该实现部分基于 Knuth [AOCP] 中对练习 69 的回答。