[Previous] [Next] [Contents]

## `Cat::IntegerListsLexClass` -- the category of combinatorial classes based on `combinat::integerListsLexTools`

#### Introduction

`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.

#### Generating the category

`Cat::IntegerListsLexClass()`

#### Categories

`Cat::CombinatorialClass`, `Cat::OrderedSet`

#### Details

- The purpose if this category is to provide an easy interface for `combinat::integerListsLexTools`. Refer to this documentation page for the description of the functionalities.

- A `Cat::IntegerListsLexClass` is a is a set of list of non-negative integers sharing the same set of constraints.

- Here, we call integer list a list `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.

- Let `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.

- Let `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`.

- A set of constraints is specified by a sequence of 6 objects `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.

- To build a domain `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`

#### Basic Entries

interfaceIntegerListsLexClass

The standard common interface of a domain that belongs to `Cat::IntegerListsLexClass`.

#### Details

- To help the writing of integers list classes, the following method is provided. It is not supposed to be called directly, but is rather here to provide default implementations.

#### Method parseOptionsIntegerListsLexClass: Parse the standard options of an integers lists Class.

- `parseOptionsIntegerListsLexClass(default constraints t, extra constr. c)`

- Each constraint is given as an equation `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.

#### Example 1

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

#### Changes

- `Cat::IntegerListsLexClass` is a new category

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package