# Enumerated set of lists of integers with constraints: base classes¶

class sage.combinat.integer_lists.base.Envelope

Bases: object

The (currently approximated) upper (lower) envelope of a function under the specified constraints.

INPUT:

• f – a function, list, or tuple; if f is a list, it is considered as the function f(i)=f[i], completed for larger $$i$$ with f(i)=max_part.
• min_part, max_part, min_slope, max_slope, … as for IntegerListsLex (please consult for details).
• sign – (+1 or -1) multiply the input values with sign and multiply the output with sign. Setting this to $$-1$$ can be used to implement a lower envelope.

The upper envelope $$U(f)$$ of $$f$$ is the (pointwise) largest function which is bounded above by $$f$$ and satisfies the max_part and max_slope conditions. Furthermore, for i,i+1<min_length, the upper envelope also satisfies the min_slope condition.

Upon computing $$U(f)(i)$$, all the previous values for $$j\leq i$$ are computed and cached; in particular $$f(i)$$ will be computed at most once for each $$i$$.

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 and max_slope conditions to always be satisfied. This is only properly defined for the restriction of $$f$$ to a finite interval $$0,..,k$$, and depends on $$k$$.
• 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_lists 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]

adapt(m, j)

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 $$m$$ at position $$j$$. Namely, this returns a function which computes, for any $$i>j$$, the minimum of the ceiling function and the value restriction given by the slope conditions.

EXAMPLES:

sage: from sage.combinat.integer_lists import Envelope
sage: f = Envelope(3)
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(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 $$i>j$$! 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(i) for i in range(10)]
[0, 1, 2, 3, 3, 3, 3, 3, 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(i) for i in range(10)]
[4, 3, 2, 1, 1, 1, 1, 1, 1, 1]
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 $$\infty$$

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 at $$i$$ for $$i$$ large enough. Special case: for a lower envelop, and when the limit is $$\infty$$, the envelope is guaranteed to tend to $$\infty$$ instead.

When s=self.limit_start() is finite, this bound is guaranteed to be valid for $$i>=s$$.

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

limit_start()

Return from which $$i$$ on the bound returned by limit holds.

limit() for the precise specifications.

EXAMPLES:

sage: from sage.combinat.integer_lists 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

max_part
max_slope
min_slope
sign
class sage.combinat.integer_lists.base.IntegerListsBackend

Bases: object

Base class for the Cython back-end of an enumerated set of lists of integers with specified constraints.

This base implements the basic operations, including checking for containment using _contains(), but not iteration. For iteration, subclass this class and implement an _iter() method.

EXAMPLES:

sage: from sage.combinat.integer_lists.base import IntegerListsBackend
sage: L = IntegerListsBackend(6, max_slope=-1)
sage: L._contains([3,2,1])
True

ceiling
floor
max_length
max_part
max_slope
max_sum
min_length
min_part
min_slope
min_sum