Brent Yorgey’s fast algorithm for integer vector (multiset) partitions.#
ALGORITHM:
Brent Yorgey, Generating Multiset Partitions, The Monad Reader, Issue 8, September 2007, p. 5.
https://wiki.haskell.org/The_Monad.Reader/Previous_issues
AUTHORS:
D. K. Sunko (2020-02-19): initial version
F. Chapoton (2020-02-22): conversion to iterators and shorter doctests and doc tweaks
T. Scrimshaw (2020-03-06): Cython optimizations and doc tweaks
- sage.combinat.fast_vector_partitions.fast_vector_partitions(v, min_vals=None)#
Brent Yorgey’s fast algorithm for integer vector (multiset) partitions.
INPUT:
v
– list of non-negative integers, understood as the vector to be partitionedmin_vals
– optional list of non-negative integers, of same length asv
OUTPUT:
A list of lists, each representing a vector partition of
v
.If
min_vals
is given, only partitions with partsp >= min_vals
in the lexicographic ordering will appear.If
min_vals
is given andlen(min_vals) != len(v)
, an error is raised.EXAMPLES:
The older the computer, the more impressive the comparison:
sage: from sage.combinat.fast_vector_partitions import fast_vector_partitions sage: fastvparts = list(fast_vector_partitions([3, 3, 3])) sage: vparts = list(VectorPartitions([3, 3, 3])) sage: vparts == fastvparts[::-1] True sage: len(fastvparts) 686 sage: list(fast_vector_partitions([1, 2, 3], min_vals=[0, 1, 1])) [[[1, 2, 3]], [[0, 2, 3], [1, 0, 0]], [[0, 2, 2], [1, 0, 1]], [[0, 2, 1], [1, 0, 2]], [[0, 2, 0], [1, 0, 3]], [[0, 1, 3], [1, 1, 0]], [[0, 1, 2], [1, 1, 1]], [[0, 1, 1], [1, 1, 2]], [[0, 1, 1], [0, 1, 2], [1, 0, 0]], [[0, 1, 1], [0, 1, 1], [1, 0, 1]]] sage: L1 = list(fast_vector_partitions([5, 7, 6], min_vals=[1, 3, 2])) sage: L1 == list(VectorPartitions([5, 7, 6], min=[1, 3, 2]))[::-1] True
Note
The partitions are returned as an iterator.
In this documentation,
a <|= b
meansa[i] <= b[i]
for alli
(notation following B. Yorgey’s paper). It is the monomial partial ordering in Dickson’s lemma:a <|= b
iffx^a
dividesx^b
as monomials.Warning
The ordering of the partitions is reversed with respect to the output of Sage class
VectorPartitions
.
- sage.combinat.fast_vector_partitions.recursive_vector_partitions(v, vL)#
Iterate over a lexicographically ordered list of lists, each list representing a vector partition of
v
, such that no part of any partition is lexicographically smaller thanvL
.Internal part of
fast_vector_partitions()
.INPUT:
v
– list of non-negative integers, understood as a vectorvL
– list of non-negative integers, understood as a vector
EXAMPLES:
sage: from sage.combinat.fast_vector_partitions import recursive_vector_partitions sage: list(recursive_vector_partitions([2, 2, 2],[1, 1, 1])) [[[2, 2, 2]], [[1, 1, 1], [1, 1, 1]]] sage: list(recursive_vector_partitions([2, 2, 2],[1, 1, 0])) [[[2, 2, 2]], [[1, 1, 1], [1, 1, 1]], [[1, 1, 0], [1, 1, 2]]] sage: list(recursive_vector_partitions([2, 2, 2],[1, 0, 1])) [[[2, 2, 2]], [[1, 1, 1], [1, 1, 1]], [[1, 1, 0], [1, 1, 2]], [[1, 0, 2], [1, 2, 0]], [[1, 0, 1], [1, 2, 1]]]
- sage.combinat.fast_vector_partitions.recursive_within_from_to(m, s, e, useS, useE)#
Iterate over a lexicographically ordered list of lists
v
satisfyinge <= v <= s
andv <|= m
as vectors.Internal part of
fast_vector_partitions()
.INPUT:
m
– list of non-negative integers, understood as a vectors
– list of non-negative integers, understood as a vectore
– list of non-negative integers, understood as a vectoruseS
– booleanuseE
– boolean
EXAMPLES:
sage: from sage.combinat.fast_vector_partitions import recursive_within_from_to sage: list(recursive_within_from_to([1, 2, 3],[1, 2, 2],[1, 1, 1],True,True)) [[1, 2, 2], [1, 2, 1], [1, 2, 0], [1, 1, 3], [1, 1, 2], [1, 1, 1]]
Note
The flags
useS
anduseE
are used to implement the condition efficiently. Because testing it loops over the vector, re-testing at each step as the vector is parsed is inefficient: all but the last comparison have been done cumulatively already. This code tests only for the last one, using the flags to accumulate information from previous calls.Warning
Expects to be called with
s <|= m
.Expects to be called first with
useS == useE == True
.
- sage.combinat.fast_vector_partitions.within_from_to(m, s, e)#
Iterate over a lexicographically ordered list of lists
v
satisfyinge <= v <= s
andv <|= m
as vectors.Internal part of
fast_vector_partitions()
.INPUT:
m
– list of non-negative integers, understood as a vectors
– list of non-negative integers, understood as a vectore
– list of non-negative integers, understood as a vector
EXAMPLES:
sage: from sage.combinat.fast_vector_partitions import within_from_to sage: list(within_from_to([1, 2, 3], [1, 2, 2], [1, 1, 1])) [[1, 2, 2], [1, 2, 1], [1, 2, 0], [1, 1, 3], [1, 1, 2], [1, 1, 1]]
Note
The input
s
will be “clipped” internally if it does not satisfy the conditions <|= m
.To understand the input check, some line art is helpful. Assume that
(a,b)
are the two least significant coordinates of some vector. Say:e = (2,3), s = (7,6), m = (9,8).
In the figure, these values are denoted by
E
,S
, andM
, while the letterX
stands for all other allowed values ofv = (a,b)
:b ^ | 8 --------X---X---X---X---X-----------M | | 7 - X X X X X | | | 6 - X X X X X S | | | 5 - X X X X X X | | | 4 - X X X X X X | | | 3 - E X X X X X | | | 2 - X X X X X | | | 1 - X X X X X | | | 0 ----|---|---X---X---X---X---X---|---|---> 0 1 2 3 4 5 6 7 8 9 a
If
S
moves horizontally, the full-height columns fill the box in untilS
reachesM
, at which point it remains the limit in the b-direction as it moves out of the box, while M takes over as the limit in the a-direction, so theM
-column remains filled only up toS
, no matter how muchS
moves further to the right.If
S
moves vertically, its column will be filled to the top of the box, but it remains the relevant limit in the a-direction, whileM
takes over in the b-direction asS
goes out of the box upwards.Both behaviors are captured by using the smaller coordinate of
S
andM
, wheneverS
is outside the box defined by M. The input will be “clipped” accordingly in that case.Warning
The “clipping” behavior is transparent to the user, but may be puzzling when comparing outputs with the function
recursive_within_from_to()
which has no input protection.