Cat::IntegerListsLexClass
--
the category of combinatorial classes based on
combinat::integerListsLexTools
Cat::IntegerListsLexClass
represents the category of combinatorial classes based on
combinat::integerListsLexTools
. It is used for lexicographic
enumeration of list of integer verifying some constraints.
This is an internal category. It is used by the special purpose
domains 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 is subject to incompatible changes anytime in the future. Use at your own risk.
Cat::IntegerListsLexClass()
Cat::CombinatorialClass
, Cat::OrderedSet
combinat::integerListsLexTools
. Refer to this documentation page for
the description of the functionalities.Cat::IntegerListsLexClass
is a is a set of list of non-negative integers sharing the
same set of constraints.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 the domains belonging to Cat::IntegerListsLexClass
is to generate all the
valid integer lists of a given sum which satisfy all the specified
constraints.
cl
that belongs to Cat::IntegerListsLexClass
the user must provide
a procedure called parseOptions
which take any argument describing
the constraints and return the sequence of constraints as defined
above. Then the category automatically implement the standard functions
isA
, count
, list
, generator
, first
,
Next
, last
, previous
, _less
. For the description
of these functions see Cat::CombinatorialClass
The standard common interface of a domain that belongs to Cat::IntegerListsLexClass
.
parseOptionsIntegerListsLexClass(default constraints t, extra constr. c)
contraints=value
where constraints is one of the
following MinLength
,MaxLength
, Length
, MinPart
,
MaxPart
, Inner
, Outer
, MinSlope
, MaxSlope
.
The set of default constraint is given as a table of such equations. Extra
constraints are given as a sequence of such equation.Here is a way to define the domain of vector of zero and one of a given
length with a given number of one. One only needs to provide the
parseOptions
functions
>> domain zeroOneVectors
inherits Dom::BaseDomain;
category Cat::IntegerListsLexClass;
parseOptions :=
proc(k)
begin
dom::parseOptionsIntegerListsLexClass
(table(Length = k,
MinPart = 0,
MaxPart = 1,
Inner = NIL,
Outer = NIL,
MinSlope = -infinity,
MaxSlope = infinity
),
args(2..args(0)));
end_proc;
end_domain:
Here is now the way to get the lists of such vectors of sum 2 and length 4.
>> zeroOneVectors::list(2, 4)
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1]]
One can now add constraints to force some element to be equal to zero or one. Here is now the way to get the lists of such vectors of sum 4 and length 6, having zeros in position 1 and 3 and ending with a one.
>> zeroOneVectors::list(4, 8, Outer = [0, 1, 0, 1, 1, 1, 1, 1],
Inner = [0, 0, 0, 0, 0, 0, 0, 1])
[[0, 1, 0, 1, 1, 0, 0, 1], [0, 1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1, 1], [0, 1, 0, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1, 0, 1], [0, 0, 0, 1, 1, 0, 1, 1], [0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1]]
Cat::IntegerListsLexClass
is a new category
MuPAD Combinat, an open source algebraic combinatorics package