combinat::integerListsLexTools
--
lexicographic generation of lists of integers
The library combinat::integerListsLexTools
provides functions for the lexicographic
generation of lists of integers under length, upper/lower bounds,
and regularity constraints.
This is an internal library. It is used by the special
purpose libraries combinat::partitions
,
combinat::compositions
, and combinat::integerVectors
which provide user-friendly interfaces.
This documentation is only provided here for the curious reader as well as for developers. The interface has been designed with efficiency in mind (no type checking, ...), and is subject to incompatible changes anytime in the future. Use at your own risk.
With the current algorithm, the constraints should satisfy the following conditions:
l
of nonnegative
integers, its parts. By abuse, infinite parts will be
allowed in some cases. The length of l
is the number
of its parts; the sum of l
is the sum of its parts.minSlope
be an integer or -infinity
and
maxSlope
be an integer or +infinity
. Then an integer
list is regular w.r.t. minSlope
and maxSlope
if
minSlope <= l[i+1]-l[i] <= maxSlope
, for all i
.
Regular functions are defined similarly.f
be a function, and l
an integer list. Then,
f
is an upper bound (resp. lower bound) for
l
if l[i]<=f(i)
(resp. f(i)<=l[i]
) for all
i
.minLength, maxLength, floor, ceiling, minSlope, maxSlope
of
the following types:
minLength
: nonnegative integer;
maxLength
: nonnegative integer or +infinity
;
floor
and ceiling
: regular functions from
[1..maxLength]
to 0..+infinity
;
minSlope
: integer or -infinity
;
maxSlope
: integer or +infinity
.
The purpose of this library is to generate all the valid integer lists of a given sum which satisfy all the specified constraints.
Two valid integer lists are considered equivalent if they only differ by trailing zeroes at positions. In this case, only the list with the least number of trailing zeroes will be generated.
The MuPAD domain used to represent integer lists: DOM_LIST
count(nonnegative integer n, constraints)
n
satisfying
constraints
.
generator(nonnegative integer n, constraints)
n
satisfying constraints
.
list(nonnegative integer n, constraints)
n
satisfying
constraints
.
first(nonnegative integer n, constraints)
n
satisfying
constraints
or FAIL
if there is none.
Next(integer list p, constraints)
p
satisfying
constraints
or FAIL
if there is none.There are 5 partitions of 4:
>> combinat::integerListsLexTools::count(
4, 0, infinity, ()->0, ()->infinity, -infinity, 0)
5
Here is the list:
>> combinat::integerListsLexTools::list(
4, 0, infinity, ()->0, ()->infinity, -infinity, 0)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
This is the list of all partitions of 7 with parts at least 2:
>> combinat::integerListsLexTools::list(
7, 0, infinity, ()->2, ()->infinity, -infinity, 0)
[[7], [5, 2], [4, 3], [3, 2, 2]]
This is the list of all partitions of 5 which are bounded
above by p:=[3,2,2]
:
>> p:=[3,2,2]:
combinat::integerListsLexTools::list(
5, 0, nops(p), ()->0, i->p[i], -infinity, 0)
[[3, 2], [3, 1, 1], [2, 2, 1]]
This is the list of all partitions of 5 which are bounded below by
p:=[2,1,1]
:
>> p:=[2,1,1]:
combinat::integerListsLexTools::list(
5, 0, nops(p), i->p[i], ()->+infinity, -infinity, 0)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1]]
This is the list of all compositions of 4:
>> combinat::integerListsLexTools::list(
4, 0, infinity, ()->1, ()->infinity, -infinity, infinity)
[[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 3 and length 3:
>> combinat::integerListsLexTools::list(
3, 3, 3, ()->0, ()->infinity, -infinity, infinity)
[[3, 0, 0], [2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 1, 1], [1, 0, 2], [0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]]
This is the list of all monomials of degree 4 which divide the
monomial x^3y^1z^2
(a monomial being represented by its
degree vector):
>> R:=Dom::DistributedPolynomial([x,y,z]):
m:=[3,1,2]:
map(combinat::integerListsLexTools::list(
4, nops(m), nops(m), ()->0, i->m[i], -infinity, infinity),
m1->R([[1,m1]]))
3 3 2 2 2 2 [x y, x z, x y z, x z , x y z ]
If maxLength=infinity
and maxSlope>0
, testing
whether there exists a valid integer list of sum n
may be
only semi-decidable. In the following example, the algorithm will
enter an infinite loop, because it needs to decide whether
ceiling(i)
is nonzero for some i
:
>> combinat::integerListsLexTools::first(
1, 0, infinity, ()->0, ()->0, -infinity, infinity)
n
of the lists. Let us know if those would be useful
features.Counting is done by brute force generation.
MuPAD Combinat, an open source algebraic combinatorics package