枚举的#
此模块包括用于枚举和计算多集分区的函数和类。
- sympy.utilities.enumerative.multiset_partitions_taocp(multiplicities)[源代码]#
枚举多集的分区。
- 参数:
multiplicities
多集组件的整数多重性列表。
- 产量:
状态
对特定分区进行编码的内部数据结构。然后，这个输出通常由一个访问者函数处理，该函数将来自该数据结构的信息与组件本身相结合，以生成一个实际的分区。
除非他们希望创建自己的访问者函数，否则用户几乎不需要查看这个数据结构的内部。但是，作为参考，它是一个包含以下组件的三元素列表：
- F
是一个帧数组，用于将pstack分成多个部分。
- L零件
指向最上面部分的底部。
- pstack公司
是PartComponent对象的数组。
这个
state输出提供了枚举函数的内部数据结构的预览。客户机应将其视为只读；对数据结构的任何修改都将导致不可预测的（几乎肯定是不正确的）结果。另外，组件state在每次迭代时进行适当的修改。因此，必须在每次循环迭代时调用访问者。积累state实例和以后处理它们将不起作用。
实例
>>> 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.iterables.multiset_partitions以multiset作为输入，直接生成multiset分区。它分派给许多函数来实现，包括这个函数。大多数用户会发现它比multiset_partitions_taocp更方便使用。
- 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的重构和扩展版本 [AOCP]. “
此类的枚举方法是生成器和返回数据结构，它们可以由用于
multiset_partitions_taocp.实例
>>> from sympy.utilities.enumerative import MultisetPartitionTraverser >>> m = MultisetPartitionTraverser() >>> m.count_partitions([4,4,4,2]) 127750 >>> m.count_partitions([3,3,3]) 686
工具书类
[Factorisatio]关于奥本海姆关于“因式分解的一个问题”E.R.坎菲尔德，保罗·埃尔多，卡尔·波默伦斯，《数论杂志》，第17卷，第1期。1983年8月。有关与Knuth算法类似的描述，请参见第7节。
[Yorgey]生成多集分区，Brent Yorgey单子阅读器，第8期，2007年9月。
- count_partitions(multiplicities)[源代码]#
返回其组件具有中给定的重数的多集的分区数
multiplicities.对于较大的计数，此方法比调用一个枚举数并计算结果要快得多。使用动态规划来减少实际探索的节点数量。用于加速计数过程的字典存储在
MultisetPartitionTraverser对象并在调用之间保持。如果用户不希望调用count_partitions对于任何其他多集，应清除该对象以节省内存。另一方面，从一次计数运行中建立的缓存可以显著加快后续对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
笔记
如果我们看看Knuth算法M的工作原理 [AOCP], 它可以看作是对部分的二叉树的遍历。一个零件有（最多）两个子零件，左子零件由展开操作产生，右子零件由减量操作产生。多集分区的普通枚举是对该树的有序遍历，其分区对应于从根到叶的路径。从路径到分区的映射有点复杂，因为分区只包含那些作为叶子或扩展链路的父级的部分，而不是那些作为递减链路的父级的部分。
出于计数目的，对叶进行计数就足够了，这可以通过递归顺序遍历来完成。植根于某个特定部分的子树的叶数只是该部分本身的函数，因此记忆有可能大大加快计数速度。
该方法采用的计算方法与假设的记忆递归函数类似，但有两个不同：
这种方法是迭代的，借用了其他枚举的结构，并保持了正在计数的部件的显式堆栈。（可能有多个集可以通过此实现快速计数，但如果使用递归实现，则会溢出默认的Python递归限制。）
而不是直接使用零件数据结构，而是构造一个更紧凑的键。更重要的是，这样可以节省一些物理部分的空间。
与枚举函数不同，当前没有count_分区的范围版本。如果有人想扩展自己的大脑，可以用计数柱状图而不是单个计数来记忆，并结合直方图来构建一个。
- enum_all(multiplicities)[源代码]#
枚举多集的分区。
实例
>>> 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']]]
参见
multiset_partitions_taocp它提供了与此方法相同的结果，但速度大约是此方法的两倍。因此，enum_all主要用于测试。关于访问者的讨论，另请参见状态和功能的讨论。
- enum_large(multiplicities, lb)[源代码]#
用lb<num（parts）枚举multiset的分区
相当于枚举范围（重数，磅，和（重数））
- 参数:
multiplicities
多集组件的多重性列表。
lb
分区中的部件数必须大于此下限。
实例
>>> 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部分。相当于枚举范围（重数，0，ub）
- 参数:
multiplicities
多集组件的多重性列表。
ub
最大零件数
实例
>>> 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']]]
实施部分基于对练习69的回答，用Knuth [AOCP].
参见