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)[source]

Brent Yorgey’s fast algorithm for integer vector (multiset) partitions.

INPUT:

  • v – list of nonnegative integers, understood as the vector to be partitioned

  • min_vals – (optional) list of nonnegative integers, of same length as v

OUTPUT: list of lists, each representing a vector partition of v

If min_vals is given, only partitions with parts p >= min_vals in the lexicographic ordering will appear.

If min_vals is given and len(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

>>> from sage.all import *
>>> from sage.combinat.fast_vector_partitions import fast_vector_partitions
>>> fastvparts = list(fast_vector_partitions([Integer(3), Integer(3), Integer(3)]))
>>> vparts = list(VectorPartitions([Integer(3), Integer(3), Integer(3)]))
>>> vparts == fastvparts[::-Integer(1)]
True
>>> len(fastvparts)
686
>>> list(fast_vector_partitions([Integer(1), Integer(2), Integer(3)], min_vals=[Integer(0), Integer(1), Integer(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]]]
>>> L1 = list(fast_vector_partitions([Integer(5), Integer(7), Integer(6)], min_vals=[Integer(1), Integer(3), Integer(2)]))
>>> L1 == list(VectorPartitions([Integer(5), Integer(7), Integer(6)], min=[Integer(1), Integer(3), Integer(2)]))[::-Integer(1)]
True

Note

The partitions are returned as an iterator.

In this documentation, a <|= b means a[i] <= b[i] for all i (notation following B. Yorgey’s paper). It is the monomial partial ordering in Dickson’s lemma: a <|= b iff x^a divides x^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)[source]

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 than vL.

Internal part of fast_vector_partitions().

INPUT:

  • v – list of nonnegative integers, understood as a vector

  • vL – list of nonnegative 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]]]

>>> from sage.all import *
>>> from sage.combinat.fast_vector_partitions import recursive_vector_partitions
>>> list(recursive_vector_partitions([Integer(2), Integer(2), Integer(2)],[Integer(1), Integer(1), Integer(1)]))
[[[2, 2, 2]], [[1, 1, 1], [1, 1, 1]]]
>>> list(recursive_vector_partitions([Integer(2), Integer(2), Integer(2)],[Integer(1), Integer(1), Integer(0)]))
[[[2, 2, 2]], [[1, 1, 1], [1, 1, 1]], [[1, 1, 0], [1, 1, 2]]]
>>> list(recursive_vector_partitions([Integer(2), Integer(2), Integer(2)],[Integer(1), Integer(0), Integer(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)[source]

Iterate over a lexicographically ordered list of lists v satisfying e <= v <= s and v <|= m as vectors.

Internal part of fast_vector_partitions().

INPUT:

  • m – list of nonnegative integers, understood as a vector

  • s – list of nonnegative integers, understood as a vector

  • e – list of nonnegative integers, understood as a vector

  • useS – boolean

  • useE – 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]]

>>> from sage.all import *
>>> from sage.combinat.fast_vector_partitions import recursive_within_from_to
>>> list(recursive_within_from_to([Integer(1), Integer(2), Integer(3)],[Integer(1), Integer(2), Integer(2)],[Integer(1), Integer(1), Integer(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 and useE 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)[source]

Iterate over a lexicographically ordered list of lists v satisfying e <= v <= s and v <|= m as vectors.

Internal part of fast_vector_partitions().

INPUT:

  • m – list of nonnegative integers, understood as a vector

  • s – list of nonnegative integers, understood as a vector

  • e – list of nonnegative 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]]

>>> from sage.all import *
>>> from sage.combinat.fast_vector_partitions import within_from_to
>>> list(within_from_to([Integer(1), Integer(2), Integer(3)], [Integer(1), Integer(2), Integer(2)], [Integer(1), Integer(1), Integer(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 condition s <|= 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, and M, while the letter X stands for all other allowed values of v = (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 until S reaches M, 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 the M-column remains filled only up to S, no matter how much S 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, while M takes over in the b-direction as S goes out of the box upwards.

Both behaviors are captured by using the smaller coordinate of S and M, whenever S 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.