Enumerative

This module includes functions and classes for enumerating and counting multiset partitions.

sympy.utilities.enumerative.multiset_partitions_taocp(multiplicities)

Enumerates partions of a multiset.

Parameters :

multiplicities :

list of integer multiplicities of the components of the multiset.

See also

sympy.utilities.iterables.multiset_partititions

Takes a multiset as input and directly yields multiset partitions. It dispatches to a number of functions, including this one, for implementation. Most users will find it more convenient to use than multiset_partitions_taocp.

Examples

>>> 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']]]

Yields

state

Internal data structure which encodes a particular partition. This output is then usually processed by a vistor function which combines the information from this data structure with the components themselves to produce an actual partition.

Unless they wish to create their own visitor function, users will have little need to look inside this data structure. But, for reference, it is a 3-element list with components:

f

is a frame array, which is used to divide pstack into parts.

lpart

points to the base of the topmost part.

pstack

is an array of PartComponent objects.

The state output offers a peek into the internal data structures of the enumeration function. The client should treat this as read-only; any modification of the data structure will cause unpredictable (and almost certainly incorrect) results. Also, the components of state are modified in place at each iteration. Hence, the visitor must be called at each loop iteration. Accumulating the state instances and processing them later will not work.

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

Use with multiset_partitions_taocp to enumerate the ways a number can be expressed as a product of factors. For this usage, the exponents of the prime factors of a number are arguments to the partition enumerator, while the corresponding prime factors are input here.

Examples

To enumerate the factorings of a number we can think of the elements of the partition as being the prime factors and the multiplicities as being their exponents.

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

Return a list of lists to represent the partition.

Examples

>>> 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]]

The approach of the function multiset_partitions_taocp is extended and generalized by the class MultisetPartitionTraverser.

class sympy.utilities.enumerative.MultisetPartitionTraverser

Has methods to enumerate and count the partitions of a multiset.

This implements a refactored and extended version of Knuth’s algorithm 7.1.2.5M [AOCP].”

The enumeration methods of this class are generators and return data structures which can be interpreted by the same visitor functions used for the output of multiset_partitions_taocp.

See also

multiset_partitions_taocp, sympy.utilities.iterables.multiset_partititions

References

[AOCP]

(1, 2, 3, 4) Algorithm 7.1.2.5M in Volume 4A, Combinatoral Algorithms, Part 1, of The Art of Computer Programming, by Donald Knuth.

[Factorisatio]

On a Problem of Oppenheim concerning “Factorisatio Numerorum” E. R. Canfield, Paul Erdos, Carl Pomerance, JOURNAL OF NUMBER THEORY, Vol. 17, No. 1. August 1983. See section 7 for a description of an algorithm similar to Knuth’s.

[Yorgey]

Generating Multiset Partitions, Brent Yorgey, The Monad.Reader, Issue 8, September 2007.

Examples

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

Returns the number of partitions of a multiset whose components have the multiplicities given in multiplicities.

For larger counts, this method is much faster than calling one of the enumerators and counting the result. Uses dynamic programming to cut down on the number of nodes actually explored. The dictionary used in order to accelerate the counting process is stored in the MultisetPartitionTraverser object and persists across calls. If the the user does not expect to call count_partitions for any additional multisets, the object should be cleared to save memory. On the other hand, the cache built up from one count run can significantly speed up subsequent calls to count_partitions, so it may be advantageous not to clear the object.

Notes

If one looks at the workings of Knuth’s algorithm M [AOCP], it can be viewed as a traversal of a binary tree of parts. A part has (up to) two children, the left child resulting from the spread operation, and the right child from the decrement operation. The ordinary enumeration of multiset partitions is an in-order traversal of this tree, and with the partitions corresponding to paths from the root to the leaves. The mapping from paths to partitions is a little complicated, since the partition would contain only those parts which are leaves or the parents of a spread link, not those which are parents of a decrement link.

For counting purposes, it is sufficient to count leaves, and this can be done with a recursive in-order traversal. The number of leaves of a subtree rooted at a particular part is a function only of that part itself, so memoizing has the potential to speed up the counting dramatically.

This method follows a computational approach which is similar to the hypothetical memoized recursive function, but with two differences:

1. This method is iterative, borrowing its structure from the other enumerations and maintaining an explicit stack of parts which are in the process of being counted. (There may be multisets which can be counted reasonably quickly by this implementation, but which would overflow the default Python recursion limit with a recursive implementation.)
2. Instead of using the part data structure directly, a more compact key is constructed. This saves space, but more importantly coalesces some parts which would remain separate with physical keys.

Unlike the enumeration functions, there is currently no _range version of count_partitions. If someone wants to stretch their brain, it should be possible to construct one by memoizing with a histogram of counts rather than a single count, and combining the histograms.

Examples

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

Enumerate the partitions of a multiset.

See also

multiset_partitions_taocp

which provides the same result as this method, but is about twice as fast. Hence, enum_all is primarily useful for testing. Also see the function for a discussion of states and visitors.

Examples

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

Enumerate the partitions of a multiset with lb < num(parts)

Equivalent to enum_range(multiplicities, lb, sum(multiplicities))

Parameters :

multiplicities :

list of multiplicities of the components of the multiset.

lb :

Number of parts in the partition must be greater than this lower bound.

See also

enum_all, enum_small, enum_range

Examples

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

Enumerate the partitions of a multiset with lb < num(parts) <= ub.

In particular, if partitions with exactly k parts are desired, call with (multiplicities, k - 1, k). This method generalizes enum_all, enum_small, and enum_large.

Examples

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

Enumerate multiset partitions with no more than ub parts.

Equivalent to enum_range(multiplicities, 0, ub)

Parameters :

multiplicities :

list of multiplicities of the components of the multiset.

ub :

Maximum number of parts

See also

enum_all, enum_large, enum_range

Examples

>>> 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']]]

The implementation is based, in part, on the answer given to exercise 69, in Knuth [AOCP].