Enumerated set of lists of integers with constraints, in inverse lexicographic order¶
IntegerListsLex
: the enumerated set of lists of nonnegative integers with specified constraints, in inverse lexicographic order.Envelope
: a utility class for upper (lower) envelope of a function under constraints.
HISTORY:
This generic tool was originally written by Hivert and Thiery in MuPAD-Combinat in 2000 and ported over to Sage by Mike Hansen in 2007. It was then completely rewritten in 2015 by Gillespie, Schilling, and Thiery, with the help of many, to deal with limitations and lack of robustness w.r.t. input.
-
class
sage.combinat.integer_list.
Envelope
(f, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, min_length=0, max_length=inf, sign=1)¶ Bases:
object
The (currently approximated) upper (lower) envelope of a function under the specified constraints.
INPUT:
f
– a function, list, or tuple; iff
is a list, it is considered as the functionf(i)=f[i]
, completed for largerwith
f(i)=max_part
.min_part
,max_part
,min_slope
,max_slope
, ... as forIntegerListsLex
(please consult for details).sign
– (+1 or -1) multiply the input values withsign
and multiply the output withsign
. Setting this tocan be used to implement a lower envelope.
The upper envelope
of
is the (pointwise) largest function which is bounded above by
and satisfies the
max_part
andmax_slope
conditions. Furthermore, fori,i+1<min_length
, the upper envelope also satisfies themin_slope
condition.Upon computing
, all the previous values for
are computed and cached; in particular
will be computed at most once for each
.
Todo
- This class is a good candidate for Cythonization, especially
to get the critical path in
__call__
super fast. - To get full envelopes, we would want both the
min_slope
andmax_slope
conditions to always be satisfied. This is only properly defined for the restriction ofto a finite interval
, and depends on
.
- This is the core “data structure” of
IntegerListsLex
. Improving the lookahead there essentially depends on having functions with a good complexity to compute the area below an envelope; and in particular how it evolves when increasing the length.
EXAMPLES:
sage: from sage.combinat.integer_list import Envelope
Trivial upper and lower envelopes:
sage: f = Envelope([3,2,2]) sage: [f(i) for i in range(10)] [3, 2, 2, inf, inf, inf, inf, inf, inf, inf] sage: f = Envelope([3,2,2], sign=-1) sage: [f(i) for i in range(10)] [3, 2, 2, 0, 0, 0, 0, 0, 0, 0]
A more interesting lower envelope:
sage: f = Envelope([4,1,5,3,5], sign=-1, min_part=2, min_slope=-1) sage: [f(i) for i in range(10)] [4, 3, 5, 4, 5, 4, 3, 2, 2, 2]
Currently, adding
max_slope
has no effect:sage: f = Envelope([4,1,5,3,5], sign=-1, min_part=2, min_slope=-1, max_slope=0) sage: [f(i) for i in range(10)] [4, 3, 5, 4, 5, 4, 3, 2, 2, 2]
unless
min_length
is large enough:sage: f = Envelope([4,1,5,3,5], sign=-1, min_part=2, min_slope=-1, max_slope=0, min_length=2) sage: [f(i) for i in range(10)] [4, 3, 5, 4, 5, 4, 3, 2, 2, 2] sage: f = Envelope([4,1,5,3,5], sign=-1, min_part=2, min_slope=-1, max_slope=0, min_length=4) sage: [f(i) for i in range(10)] [5, 5, 5, 4, 5, 4, 3, 2, 2, 2] sage: f = Envelope([4,1,5,3,5], sign=-1, min_part=2, min_slope=-1, max_slope=0, min_length=5) sage: [f(i) for i in range(10)] [5, 5, 5, 5, 5, 4, 3, 2, 2, 2]
A non trivial upper envelope:
sage: f = Envelope([9,1,5,4], max_part=7, max_slope=2) sage: [f(i) for i in range(10)] [7, 1, 3, 4, 6, 7, 7, 7, 7, 7]
TESTS:
sage: f = Envelope(3, min_slope=1) sage: [f(i) for i in range(10)] [3, 3, 3, 3, 3, 3, 3, 3, 3, 3] sage: f = Envelope(3, min_slope=1, min_length=5) sage: [f(i) for i in range(10)] [-1, 0, 1, 2, 3, 3, 3, 3, 3, 3] sage: f = Envelope(3, sign=-1, min_slope=1) sage: [f(i) for i in range(10)] [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: f = Envelope(3, sign=-1, max_slope=-1, min_length=4) sage: [f(i) for i in range(10)] [6, 5, 4, 3, 3, 3, 3, 3, 3, 3]
-
__init__
(f, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, min_length=0, max_length=inf, sign=1)¶ Initialize this envelope.
TESTS:
sage: from sage.combinat.integer_list import Envelope sage: f = Envelope(3, sign=-1, max_slope=-1, min_length=4) sage: f.__dict__ {'_f': The constant function (...) -> inf, '_f_limit_start': 0, '_max_part': -3, '_max_slope': inf, '_min_slope': 1, '_precomputed': [-6, -5, -4, -3], '_sign': -1} sage: TestSuite(f).run(skip="_test_pickling") sage: Envelope(3, sign=1/3, max_slope=-1, min_length=4) Traceback (most recent call last): ... TypeError: no conversion of this rational to integer sage: Envelope(3, sign=-2, max_slope=-1, min_length=4) Traceback (most recent call last): ... ValueError: sign should be +1 or -1
-
adapt
(m, j)¶ Return this envelope adapted to an additional local constraint.
INPUT:
m
– a nonnegative integer (starting value)j
– a nonnegative integer (position)
This method adapts this envelope to the additional local constraint imposed by having a part
at position
. Namely, this returns a function which computes, for any
, the minimum of the ceiling function and the value restriction given by the slope conditions.
EXAMPLES:
sage: from sage.combinat.integer_list import Envelope sage: f = Envelope(3) sage: g = f.adapt(1,1) sage: g is f True sage: [g(i) for i in range(10)] [3, 3, 3, 3, 3, 3, 3, 3, 3, 3] sage: f = Envelope(3, max_slope=1) sage: g = f.adapt(1,1) sage: [g(i) for i in range(10)] [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]
Note that, in both cases above, the adapted envelope is only guaranteed to be valid for
! This is to leave potential room in the future for sharing similar adapted envelopes:
sage: g = f.adapt(0,0) sage: [g(i) for i in range(10)] [0, 1, 2, 3, 3, 3, 3, 3, 3, 3] sage: g = f.adapt(2,2) sage: [g(i) for i in range(10)] [0, 1, 2, 3, 3, 3, 3, 3, 3, 3] sage: g = f.adapt(3,3) sage: [g(i) for i in range(10)] [0, 1, 2, 3, 3, 3, 3, 3, 3, 3]
Now with a lower envelope:
sage: f = Envelope(1, sign=-1, min_slope=-1) sage: g = f.adapt(2,2) sage: [g(i) for i in range(10)] [4, 3, 2, 1, 1, 1, 1, 1, 1, 1] sage: g = f.adapt(1,3) sage: [g(i) for i in range(10)] [4, 3, 2, 1, 1, 1, 1, 1, 1, 1]
-
limit
()¶ Return a bound on the limit of
self
.OUTPUT: a nonnegative integer or
This returns some upper bound for the accumulation points of this upper envelope. For a lower envelope, a lower bound is returned instead.
In particular this gives a bound for the value of
self
atfor
large enough. Special case: for a lower envelop, and when the limit is
, the envelope is guaranteed to tend to
instead.
When
s=self.limit_start()
is finite, this bound is guaranteed to be valid for.
Sometimes it’s better to have a loose bound that starts early; sometimes the converse holds. At this point which specific bound and starting point is returned is not set in stone, in order to leave room for later optimizations.
EXAMPLES:
sage: from sage.combinat.integer_list import Envelope sage: Envelope([4,1,5]).limit() inf sage: Envelope([4,1,5], max_part=2).limit() 2 sage: Envelope([4,1,5], max_slope=0).limit() 1 sage: Envelope(lambda x: 3, max_part=2).limit() 2
Lower envelopes:
sage: Envelope(lambda x: 3, min_part=2, sign=-1).limit() 2 sage: Envelope([4,1,5], min_slope=0, sign=-1).limit() 5 sage: Envelope([4,1,5], sign=-1).limit() 0
See also
-
limit_start
()¶ Return from which
on the bound returned by
limit
holds.See also
limit()
for the precise specifications.EXAMPLES:
sage: from sage.combinat.integer_list import Envelope sage: Envelope([4,1,5]).limit_start() 3 sage: Envelope([4,1,5], sign=-1).limit_start() 3 sage: Envelope([4,1,5], max_part=2).limit_start() 3 sage: Envelope(4).limit_start() 0 sage: Envelope(4, sign=-1).limit_start() 0 sage: Envelope(lambda x: 3).limit_start() == Infinity True sage: Envelope(lambda x: 3, max_part=2).limit_start() == Infinity True sage: Envelope(lambda x: 3, sign=-1, min_part=2).limit_start() == Infinity True
-
class
sage.combinat.integer_list.
IntegerListsLex
(n=None, length=None, min_length=0, max_length=inf, floor=None, ceiling=None, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, min_sum=0, max_sum=inf, name=None, category=None, element_constructor=None, element_class=None, global_options=None, check=True)¶ Bases:
sage.structure.parent.Parent
Lists of nonnegative integers with constraints, in inverse lexicographic order.
An integer list is a list
of nonnegative integers, its parts. The slope (at position
) is the difference
l[i+1]-l[i]
between two consecutive parts.This class allows to construct the set
of all integer lists
satisfying specified bounds on the sum, the length, the slope, and the individual parts, enumerated in inverse lexicographic order, that is from largest to smallest in lexicographic order. Note that, to admit such an enumeration,
is almost necessarily finite (see IntegerListsLex_finiteness).
The main purpose is to provide a generic iteration engine for all the enumerated sets like
Partitions
,Compositions
,IntegerVectors
. It can also be used to generate many other combinatorial objects like Dyck paths, Motzkin paths, etc. Mathematically speaking, this is a special case of set of integral points of a polytope (or union thereof, when the length is not fixed).INPUT:
min_sum
– a nonnegative integer (default: 0): a lower bound onsum(l)
.max_sum
– a nonnegative integer or(default:
): an upper bound on
sum(l)
.n
– a nonnegative integer (optional): if specified, this overridesmin_sum
andmax_sum
.min_length
– a nonnegative integer (default:): a lower bound on
len(l)
.max_length
– a nonnegative integer or(default:
): an upper bound on
len(l)
.length
– an integer (optional); overridesmin_length
andmax_length
if specified;min_part
– a nonnegative integer: a lower bounds on allparts:
min_part <= l[i]
for0 <= i < len(l)
.
floor
– a list of nonnegative integers or a function: lower bounds on the individual parts.
If
floor
is a list of integers, thenfloor<=l[i]
for0 <= i < min(len(l), len(floor)
. Similarly, iffloor
is a function, thenfloor(i) <= l[i]
for0 <= i < len(l)
.max_part
– a nonnegative integer or: an upper bound on all parts:
l[i] <= max_part
for0 <= i < len(l)
.ceiling
– upper bounds on the individual partsl[i]
; this takes the same type of input asfloor
, except thatis allowed in addition to integers, and the default value is
.
min_slope
– an integer or(default:
): an lower bound on the slope between consecutive parts:
min_slope <= l[i+1]-l[i]
for0 <= i < len(l)-1
max_slope
– an integer or(defaults:
) an upper bound on the slope between consecutive parts:
l[i+1]-l[i] <= max_slope
for0 <= i < len(l)-1
category
– a category (default:FiniteEnumeratedSets
)check
– boolean (default:True
): whether to display the warnings raised when functions are given as input tofloor
orceiling
and the errors raised when there is no proper enumeration.name
– a string orNone
(default:None
) if set, this will be passed down toParent.rename()
to specify the name ofself
. It is recommented to use directly the rename method as this feature may become deprecated.element_constructor
– a function (or callable) that creates elements ofself
from a list. See alsoParent
.element_class
– a class for the elements ofself
(default:). This merely sets the attribute
self.Element
. See the examples for details.global_options
– aGlobalOptions
object that will be assigned to the attribute_global_options
; for internal use only (subclasses, ...).
Note
When several lists satisfying the constraints differ only by trailing zeroes, only the shortest one is enumerated (and therefore counted). The others are still considered valid. See the examples below.
This feature is questionable. It is recommended not to rely on it, as it may eventually be discontinued.
EXAMPLES:
We create the enumerated set of all lists of nonnegative integers of length
and sum
:
sage: C = IntegerListsLex(2, length=3) sage: C Integer lists of sum 2 satisfying certain constraints sage: C.cardinality() 6 sage: [p for p in C] [[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]] sage: [2, 0, 0] in C True sage: [2, 0, 1] in C False sage: "a" in C False sage: ["a"] in C False sage: C.first() [2, 0, 0]
One can specify lower and upper bounds on each part:
sage: list(IntegerListsLex(5, length=3, floor=[1,2,0], ceiling=[3,2,3])) [[3, 2, 0], [2, 2, 1], [1, 2, 2]]
When the length is fixed as above, one can also use
IntegerVectors
:sage: IntegerVectors(2,3).list() [[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]
Using the slope condition, one can generate integer partitions (but see
Partitions
):sage: list(IntegerListsLex(4, max_slope=0)) [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
The following is the list of all partitions of
with parts at least
:
sage: list(IntegerListsLex(7, max_slope=0, min_part=2)) [[7], [5, 2], [4, 3], [3, 2, 2]]
floor and ceiling conditions
Next we list all partitions of
of length at most
which are bounded below by
[2,1,1]
:sage: list(IntegerListsLex(5, max_slope=0, max_length=3, floor=[2,1,1])) [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1]]
Note that
[5]
is considered valid, because the floor constraints only apply to existing positions in the list. To obtain instead the partitions containing[2,1,1]
, one needs to usemin_length
orlength
:sage: list(IntegerListsLex(5, max_slope=0, length=3, floor=[2,1,1])) [[3, 1, 1], [2, 2, 1]]
Here is the list of all partitions of
which are contained in
[3,2,2]
:sage: list(IntegerListsLex(5, max_slope=0, max_length=3, ceiling=[3,2,2])) [[3, 2], [3, 1, 1], [2, 2, 1]]
This is the list of all compositions of
(but see
Compositions
):sage: list(IntegerListsLex(4, min_part=1)) [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
This is the list of all integer vectors of sum
and length
:
sage: list(IntegerListsLex(4, length=3)) [[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1], [2, 0, 2], [1, 3, 0], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
For whatever it is worth, the
floor
andmin_part
constraints can be combined:sage: L = IntegerListsLex(5, floor=[2,0,2], min_part=1) sage: L.list() [[5], [4, 1], [3, 2], [2, 3], [2, 1, 2]]
This is achieved by updating the floor upon constructing
L
:sage: [L._floor(i) for i in range(5)] [2, 1, 2, 1, 1]
Similarly, the
ceiling
andmax_part
constraints can be combined:sage: L = IntegerListsLex(4, ceiling=[2,3,1], max_part=2, length=3) sage: L.list() [[2, 2, 0], [2, 1, 1], [1, 2, 1]] sage: [L._ceiling(i) for i in range(5)] [2, 2, 1, 2, 2]
This can be used to generate Motzkin words (see Wikipedia article Motzkin_number):
sage: def motzkin_words(n): ....: return IntegerListsLex(length=n+1, min_slope=-1, max_slope=1, ....: ceiling=[0]+[+oo for i in range(n-1)]+[0]) sage: motzkin_words(4).list() [[0, 1, 2, 1, 0], [0, 1, 1, 1, 0], [0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]] sage: [motzkin_words(n).cardinality() for n in range(8)] [1, 1, 2, 4, 9, 21, 51, 127] sage: oeis(_) # optional -- internet 0: A001006: Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.
or Dyck words (see also
DyckWords
), through the bijection with paths fromto
with left and up steps that remain below the diagonal:
sage: def dyck_words(n): ....: return IntegerListsLex(length=n, ceiling=range(n+1), min_slope=0) sage: [dyck_words(n).cardinality() for n in range(8)] [1, 1, 2, 5, 14, 42, 132, 429] sage: dyck_words(3).list() [[0, 1, 2], [0, 1, 1], [0, 0, 2], [0, 0, 1], [0, 0, 0]]
On finiteness and inverse lexicographic enumeration
The set of all lists of integers cannot be enumerated in inverse lexicographic order, since there is no largest list (take
for
as large as desired):
sage: IntegerListsLex().first() Traceback (most recent call last): ... ValueError: Could not prove that the specified constraints yield a finite set
Here is a variant which could be enumerated in lexicographic order but not in inverse lexicographic order:
sage: L = IntegerListsLex(length=2, ceiling=[Infinity, 0], floor=[0,1]) sage: for l in L: print l Traceback (most recent call last): ... ValueError: infinite upper bound for values of m
Even when the sum is specified, it is not necessarily possible to enumerate all elements in inverse lexicographic order. In the following example, the list
[1, 1, 1]
will never appear in the enumeration:sage: IntegerListsLex(3).first() Traceback (most recent call last): ... ValueError: Could not prove that the specified constraints yield a finite set
If one wants to proceed anyway, one can sign a waiver by setting
check=False
(again, be warned that some valid lists may never appear):sage: L = IntegerListsLex(3, check=False) sage: it = iter(L) sage: [next(it) for i in range(6)] [[3], [2, 1], [2, 0, 1], [2, 0, 0, 1], [2, 0, 0, 0, 1], [2, 0, 0, 0, 0, 1]]
In fact, being inverse lexicographically enumerable is almost equivalent to being finite. The only infinity that can occur would be from a tail of numbers
as in the previous example, where the
moves further and further to the right. If there is any list that is inverse lexicographically smaller than such a configuration, the iterator would not reach it and hence would not be considered iterable. Given that the infinite cases are very specific, at this point only the finite cases are supported (without signing the waiver).
The finiteness detection is not complete yet, so some finite cases may not be supported either, at least not without disabling the checks. Practical examples of such are welcome.
On trailing zeroes, and their caveats
As mentioned above, when several lists satisfying the constraints differ only by trailing zeroes, only the shortest one is listed:
sage: L = IntegerListsLex(max_length=4, max_part=1) sage: L.list() [[1, 1, 1, 1], [1, 1, 1], [1, 1, 0, 1], [1, 1], [1, 0, 1, 1], [1, 0, 1], [1, 0, 0, 1], [1], [0, 1, 1, 1], [0, 1, 1], [0, 1, 0, 1], [0, 1], [0, 0, 1, 1], [0, 0, 1], [0, 0, 0, 1], []]
and counted:
sage: L.cardinality() 16
Still, the others are considered as elements of
:
sage: L = IntegerListsLex(4,min_length=3,max_length=4) sage: L.list() [..., [2, 2, 0], ...] sage: [2, 2, 0] in L # in L.list() True sage: [2, 2, 0, 0] in L # not in L.list() ! True sage: [2, 2, 0, 0, 0] in L False
Specifying functions as input for the floor or ceiling
We construct all lists of sum
and length
such that
l[i] <= i
:sage: list(IntegerListsLex(4, length=4, ceiling=lambda i: i, check=False)) [[0, 1, 2, 1], [0, 1, 1, 2], [0, 1, 0, 3], [0, 0, 2, 2], [0, 0, 1, 3]]
Warning
When passing a function as
floor
orceiling
, it may become undecidable to detect improper inverse lexicographic enumeration. For example, the following example has a finite enumeration:sage: L = IntegerListsLex(3, floor=lambda i: 1 if i>=2 else 0, check=False) sage: L.list() [[3], [2, 1], [2, 0, 1], [1, 2], [1, 1, 1], [1, 0, 2], [1, 0, 1, 1], [0, 3], [0, 2, 1], [0, 1, 2], [0, 1, 1, 1], [0, 0, 3], [0, 0, 2, 1], [0, 0, 1, 2], [0, 0, 1, 1, 1]]
but one cannot decide whether the following has an improper inverse lexicographic enumeration without computing the floor all the way to
Infinity
:sage: L = IntegerListsLex(3, floor=lambda i: 0, check=False) sage: it = iter(L) sage: [next(it) for i in range(6)] [[3], [2, 1], [2, 0, 1], [2, 0, 0, 1], [2, 0, 0, 0, 1], [2, 0, 0, 0, 0, 1]]
Hence a warning is raised when a function is specified as input, unless the waiver is signed by setting
check=False
:sage: L = IntegerListsLex(3, floor=lambda i: 1 if i>=2 else 0) doctest:... A function has been given as input of the floor=[...] or ceiling=[...] arguments of IntegerListsLex. Please see the documentation for the caveats. If you know what you are doing, you can set check=False to skip this warning.
Similarly, the algorithm may need to search forever for a solution when the ceiling is ultimately zero:
sage: L = IntegerListsLex(2,ceiling=lambda i:0, check=False) sage: L.first() # not tested: will hang forever sage: L = IntegerListsLex(2,ceiling=lambda i:0 if i<20 else 1, check=False) sage: it = iter(L) sage: next(it) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1] sage: next(it) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1] sage: next(it) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Tip: using disjoint union enumerated sets for additional flexibility
Sometimes, specifying a range for the sum or the length may be too restrictive. One would want instead to specify a list, or iterable
, of acceptable values. This is easy to achieve using a
disjoint union of enumerated sets
. Here we want to accept the values:
sage: C = DisjointUnionEnumeratedSets(Family([0,2,3], ....: lambda n: IntegerListsLex(n, length=2))) sage: C Disjoint union of Finite family {0: Integer lists of sum 0 satisfying certain constraints, 2: Integer lists of sum 2 satisfying certain constraints, 3: Integer lists of sum 3 satisfying certain constraints} sage: C.list() [[0, 0], [2, 0], [1, 1], [0, 2], [3, 0], [2, 1], [1, 2], [0, 3]]
The price to pay is that the enumeration order is now graded lexicographic instead of lexicographic: first choose the value according to the order specified by
, and use lexicographic order within each value. Here is we reverse
:
sage: DisjointUnionEnumeratedSets(Family([3,2,0], ....: lambda n: IntegerListsLex(n, length=2))).list() [[3, 0], [2, 1], [1, 2], [0, 3], [2, 0], [1, 1], [0, 2], [0, 0]]
Note that if a given value appears several times, the corresponding elements will be enumerated several times, which may, or not, be what one wants:
sage: DisjointUnionEnumeratedSets(Family([2,2], ....: lambda n: IntegerListsLex(n, length=2))).list() [[2, 0], [1, 1], [0, 2], [2, 0], [1, 1], [0, 2]]
Here is a variant where we specify acceptable values for the length:
sage: DisjointUnionEnumeratedSets(Family([0,1,3], ....: lambda l: IntegerListsLex(2, length=l))).list() [[2], [2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]
This technique can also be useful to obtain a proper enumeration on infinite sets by using a graded lexicographic enumeration:
sage: C = DisjointUnionEnumeratedSets(Family(NN, ....: lambda n: IntegerListsLex(n, length=2))) sage: C Disjoint union of Lazy family (<lambda>(i))_{i in Non negative integer semiring} sage: it = iter(C) sage: [next(it) for i in range(10)] [[0, 0], [1, 0], [0, 1], [2, 0], [1, 1], [0, 2], [3, 0], [2, 1], [1, 2], [0, 3]]
Specifying how to construct elements
This is the list of all monomials of degree
which divide the monomial
(a monomial being identified with its exponent vector):
sage: R.<x,y,z> = QQ[] sage: m = [3,1,2] sage: def term(exponents): ....: return x^exponents[0] * y^exponents[1] * z^exponents[2] sage: list( IntegerListsLex(4, length=len(m), ceiling=m, element_constructor=term) ) [x^3*y, x^3*z, x^2*y*z, x^2*z^2, x*y*z^2]
Note the use of the
element_constructor
option to specify how to construct elements from a plain list.A variant is to specify a class for the elements. With the default element constructor, this class should take as input the parent
self
and a list. Here we want the elements to be constructed in the classPartition
:sage: IntegerListsLex(3, max_slope=0, element_class=Partition, global_options=Partitions.global_options).list() [[3], [2, 1], [1, 1, 1]]
Note that the
Partition
further assumes the existence of an attribute_global_options
in the parent, hence the use of theglobal_options
parameter.Warning
The protocol for specifying the element class and constructor is subject to changes.
ALGORITHM:
The iteration algorithm uses a depth first search through the prefix tree of the list of integers (see also Lexicographic generation of lists of integers). While doing so, it does some lookahead heuristics to attempt to cut dead branches.
In most practical use cases, most dead branches are cut. Then, roughly speaking, the time needed to iterate through all the elements of
is proportional to the number of elements, where the proportion factor is controlled by the length
of the longest element of
. In addition, the memory usage is also controlled by
, which is to say negligible in practice.
Still, there remains much room for efficiency improvements; see trac ticket #18055, trac ticket #18056.
Note
The generation algorithm could in principle be extended to deal with non-constant slope constraints and with negative parts.
TESTS:
This example from the combinatorics tutorial used to fail before trac ticket #17979 because the floor conditions did not satisfy the slope conditions:
sage: I = IntegerListsLex(16, min_length=2, max_slope=-1, floor=[5,3,3]) sage: I.list() [[13, 3], [12, 4], [11, 5], [10, 6], [9, 7], [9, 4, 3], [8, 5, 3], [8, 4, 3, 1], [7, 6, 3], [7, 5, 4], [7, 5, 3, 1], [7, 4, 3, 2], [6, 5, 4, 1], [6, 5, 3, 2], [6, 4, 3, 2, 1]]
sage: Partitions(2, max_slope=-1, length=2).list() [] sage: list(IntegerListsLex(0, floor=ConstantFunction(1), min_slope=0)) [[]] sage: list(IntegerListsLex(0, floor=ConstantFunction(1), min_slope=0, max_slope=0)) [[]] sage: list(IntegerListsLex(0, max_length=0, floor=ConstantFunction(1), min_slope=0, max_slope=0)) [[]] sage: list(IntegerListsLex(0, max_length=0, floor=ConstantFunction(0), min_slope=0, max_slope=0)) [[]] sage: list(IntegerListsLex(0, min_part=1, min_slope=0)) [[]] sage: list(IntegerListsLex(1, min_part=1, min_slope=0)) [[1]] sage: list(IntegerListsLex(0, min_length=1, min_part=1, min_slope=0)) [] sage: list(IntegerListsLex(0, min_length=1, min_slope=0)) [[0]] sage: list(IntegerListsLex(3, max_length=2)) [[3], [2, 1], [1, 2], [0, 3]] sage: partitions = {"min_part": 1, "max_slope": 0} sage: partitions_min_2 = {"floor": ConstantFunction(2), "max_slope": 0} sage: compositions = {"min_part": 1} sage: integer_vectors = lambda l: {"length": l} sage: lower_monomials = lambda c: {"length": c, "floor": lambda i: c[i]} sage: upper_monomials = lambda c: {"length": c, "ceiling": lambda i: c[i]} sage: constraints = { "min_part":1, "min_slope": -1, "max_slope": 0} sage: list(IntegerListsLex(6, **partitions)) [[6], [5, 1], [4, 2], [4, 1, 1], [3, 3], [3, 2, 1], [3, 1, 1, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] sage: list(IntegerListsLex(6, **constraints)) [[6], [3, 3], [3, 2, 1], [2, 2, 2], [2, 2, 1, 1], [2, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]] sage: list(IntegerListsLex(1, **partitions_min_2)) [] sage: list(IntegerListsLex(2, **partitions_min_2)) [[2]] sage: list(IntegerListsLex(3, **partitions_min_2)) [[3]] sage: list(IntegerListsLex(4, **partitions_min_2)) [[4], [2, 2]] sage: list(IntegerListsLex(5, **partitions_min_2)) [[5], [3, 2]] sage: list(IntegerListsLex(6, **partitions_min_2)) [[6], [4, 2], [3, 3], [2, 2, 2]] sage: list(IntegerListsLex(7, **partitions_min_2)) [[7], [5, 2], [4, 3], [3, 2, 2]] sage: list(IntegerListsLex(9, **partitions_min_2)) [[9], [7, 2], [6, 3], [5, 4], [5, 2, 2], [4, 3, 2], [3, 3, 3], [3, 2, 2, 2]] sage: list(IntegerListsLex(10, **partitions_min_2)) [[10], [8, 2], [7, 3], [6, 4], [6, 2, 2], [5, 5], [5, 3, 2], [4, 4, 2], [4, 3, 3], [4, 2, 2, 2], [3, 3, 2, 2], [2, 2, 2, 2, 2]] sage: list(IntegerListsLex(4, **compositions)) [[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]] sage: list(IntegerListsLex(6, min_length=1, floor=[7])) [] sage: L = IntegerListsLex(10**100,length=1) sage: L.list() [[10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]]
Noted on trac ticket #17898:
sage: list(IntegerListsLex(4, min_part=1, length=3, min_slope=1)) [] sage: IntegerListsLex(6, ceiling=[4,2], floor=[3,3]).list() [] sage: IntegerListsLex(6, min_part=1, max_part=3, max_slope=-4).list() []
Noted in trac ticket #17548, which are now fixed:
sage: IntegerListsLex(10, min_part=2, max_slope=-1).list() [[10], [8, 2], [7, 3], [6, 4], [5, 3, 2]] sage: IntegerListsLex(5, min_slope=1, floor=[2,1,1], max_part=2).list() [] sage: IntegerListsLex(4, min_slope=0, max_slope=0).list() [[4], [2, 2], [1, 1, 1, 1]] sage: IntegerListsLex(6, min_slope=-1, max_slope=-1).list() [[6], [3, 2, 1]] sage: IntegerListsLex(6, min_length=3, max_length=2, min_part=1).list() [] sage: I = IntegerListsLex(3, max_length=2, min_part=1) sage: I.list() [[3], [2, 1], [1, 2]] sage: [1,1,1] in I False sage: I=IntegerListsLex(10, ceiling=[4], max_length=1, min_part=1) sage: I.list() [] sage: [4,6] in I False sage: I = IntegerListsLex(4, min_slope=1, min_part=1, max_part=2) sage: I.list() [] sage: I = IntegerListsLex(7, min_slope=1, min_part=1, max_part=4) sage: I.list() [[3, 4], [1, 2, 4]] sage: I = IntegerListsLex(4, floor=[2,1], ceiling=[2,2], max_length=2, min_slope=0) sage: I.list() [[2, 2]] sage: I = IntegerListsLex(10, min_part=1, max_slope=-1) sage: I.list() [[10], [9, 1], [8, 2], [7, 3], [7, 2, 1], [6, 4], [6, 3, 1], [5, 4, 1], [5, 3, 2], [4, 3, 2, 1]]
TESTS from comments on trac ticket #17979
Comment 191:
sage: list(IntegerListsLex(1, min_length=2, min_slope=0, max_slope=0)) []
Comment 240:
sage: L = IntegerListsLex(min_length=2, max_part=0) sage: L.list() [[0, 0]]
Tests on the element constructor feature and mutability
Internally, the iterator works on a single list that is mutated along the way. The following test makes sure that we actually make a copy of this list before passing it to
element_constructor
in order to avoid reference effects:sage: from sage.misc.c3_controlled import identity sage: P = IntegerListsLex(n=3, max_slope=0, min_part=1, element_constructor=identity) sage: list(P) [[3], [2, 1], [1, 1, 1]]
Same, step by step:
sage: it = iter(P) sage: a = next(it); a [3] sage: b = next(it); b [2, 1] sage: a [3] sage: a is b False
Tests from MuPAD-Combinat:
sage: IntegerListsLex(7, min_length=2, max_length=6, floor=[0,0,2,0,0,1], ceiling=[3,2,3,2,1,2]).cardinality() 83 sage: IntegerListsLex(7, min_length=2, max_length=6, floor=[0,0,2,0,1,1], ceiling=[3,2,3,2,1,2]).cardinality() 53 sage: IntegerListsLex(5, min_length=2, max_length=6, floor=[0,0,2,0,0,0], ceiling=[2,2,2,2,2,2]).cardinality() 30 sage: IntegerListsLex(5, min_length=2, max_length=6, floor=[0,0,1,1,0,0], ceiling=[2,2,2,2,2,2]).cardinality() 43 sage: IntegerListsLex(0, min_length=0, max_length=7, floor=[1,1,0,0,1,0], ceiling=[4,3,2,3,2,2,1]).first() [] sage: IntegerListsLex(0, min_length=1, max_length=7, floor=[0,1,0,0,1,0], ceiling=[4,3,2,3,2,2,1]).first() [0] sage: IntegerListsLex(0, min_length=1, max_length=7, floor=[1,1,0,0,1,0], ceiling=[4,3,2,3,2,2,1]).cardinality() 0 sage: IntegerListsLex(2, min_length=0, max_length=7, floor=[1,1,0,0,0,0], ceiling=[4,3,2,3,2,2,1]).first() # Was [1,1], due to slightly different specs [2] sage: IntegerListsLex(1, min_length=1, max_length=7, floor=[1,1,0,0,0,0], ceiling=[4,3,2,3,2,2,1]).first() [1] sage: IntegerListsLex(1, min_length=2, max_length=7, floor=[1,1,0,0,0,0], ceiling=[4,3,2,3,2,2,1]).cardinality() 0 sage: IntegerListsLex(2, min_length=5, max_length=7, floor=[1,1,0,0,0,0], ceiling=[4,3,2,3,2,2,1]).first() [1, 1, 0, 0, 0] sage: IntegerListsLex(2, min_length=5, max_length=7, floor=[1,1,0,0,0,1], ceiling=[4,3,2,3,2,2,1]).first() [1, 1, 0, 0, 0] sage: IntegerListsLex(2, min_length=5, max_length=7, floor=[1,1,0,0,1,0], ceiling=[4,3,2,3,2,2,1]).cardinality() 0 sage: IntegerListsLex(4, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).cardinality() 0 sage: IntegerListsLex(5, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).first() [2, 1, 2] sage: IntegerListsLex(6, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).first() [3, 1, 2] sage: IntegerListsLex(12, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).first() [3, 1, 2, 3, 2, 1] sage: IntegerListsLex(13, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).first() [3, 1, 2, 3, 2, 2] sage: IntegerListsLex(14, min_length=3, max_length=6, floor=[2, 1, 2, 1, 1, 1], ceiling=[3, 1, 2, 3, 2, 2]).cardinality() 0
This used to hang (see comment 389 and fix in
Envelope.__init__()
):sage: IntegerListsLex(7, max_part=0, ceiling=lambda i:i, check=False).list() []
-
class
Element
¶ Bases:
sage.structure.list_clone.ClonableArray
Element class for
IntegerListsLex
.-
check
()¶ Check to make sure this is a valid element in its
IntegerListsLex
parent.EXAMPLES:
sage: C = IntegerListsLex(4) sage: C([4]).check() True sage: C([5]).check() # not implemented False
-
-
class
sage.combinat.integer_list.
IntegerListsLexIter
(parent)¶ Iterator class for IntegerListsLex.
Let
T
be the prefix tree of all lists of nonnegative integers that satisfy all constraints except possibly formin_length
andmin_sum
; let the children of a list be sorted decreasingly according to their last part.The iterator is based on a depth-first search exploration of a subtree of this tree, trying to cut branches that do not contain a valid list. Each call of
next
iterates through the nodes of this tree until it finds a valid list to return.Here are the attributes describing the current state of the iterator, and their invariants:
_parent
– theIntegerListsLex
object this is iterating on;_current_list
– the list corresponding to the current node of the tree;_j
– the index of the last element of_current_list
:self._j == len(self._current_list) - 1
;_current_sum
– the sum of the parts of_current_list
;_search_ranges
– a list of same length as_current_list
: the range for each part.
Furthermore, we assume that there is no obvious contradiction in the contraints:
self._parent._min_length <= self._parent._max_length
;self._parent._min_slope <= self._parent._max_slope
unlessself._parent._min_length <= 1
.
Along this iteration,
next
switches between the following states:- LOOKAHEAD: determine whether the current list could be a prefix of a valid list;
- PUSH: go deeper into the prefix tree by appending the largest possible part to the current list;
- ME: check whether the current list is valid and if yes return it
- DECREASE: decrease the last part;
- POP: pop the last part of the current list;
- STOP: the iteration is finished.
The attribute
_next_state
contains the next statenext
should enter in.-
next
()¶ Return the next element in the iteration.
EXAMPLES:
sage: from sage.combinat.integer_list import IntegerListsLexIter sage: C = IntegerListsLex(2, length=3) sage: I = IntegerListsLexIter(C) sage: next(I) [2, 0, 0] sage: next(I) [1, 1, 0]
-
sage.combinat.integer_list.
IntegerListsNN
(**kwds)¶ Lists of nonnegative integers with constraints.
This function returns the union of
IntegerListsLex(n, **kwds)
whereranges over all nonnegative integers.
Warning
this function is likely to disappear in trac ticket #17927.
EXAMPLES:
sage: from sage.combinat.integer_list import IntegerListsNN sage: L = IntegerListsNN(max_length=3, max_slope=-1) sage: L Disjoint union of Lazy family (<lambda>(i))_{i in Non negative integer semiring} sage: it = iter(L) sage: for _ in range(20): ....: print next(it) [] [1] [2] [3] [2, 1] [4] [3, 1] [5] [4, 1] [3, 2] [6] [5, 1] [4, 2] [3, 2, 1] [7] [6, 1] [5, 2] [4, 3] [4, 2, 1] [8]