[Previous] [Next] [Contents]

## `combinat::integerListsLexTools` -- lexicographic generation of lists of integers

#### Introduction

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:

- The upper and lower bounds themselves should satisfy the regularity constraints.
- The maximal and minimal slopes values should not be equal.
- The maximal and minimal part values should not be equal.

Those conditions are not checked by the algorithm, and the result may be completely incorrect if they are not satisfied.

#### Details

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

#### Entries

domtype

The MuPAD domain used to represent integer lists: `DOM_LIST`

#### Method count: number of valid integer lists

- `count(nonnegative integer n, constraints)`

- Returns the number of integer lists of sum `n` satisfying `constraints`.

#### Method generator: generator for valid integer lists

- `generator(nonnegative integer n, constraints)`

- Returns a generator for the integer lists of sum `n` satisfying `constraints`.

#### Method list: list of the valid integer lists

- `list(nonnegative integer n, constraints)`

- Returns the list of the integer lists of sum `n` satisfying `constraints`.

#### Method first: first valid integer list

- `first(nonnegative integer n, constraints)`

- Returns the first integer list of sum `n` satisfying `constraints` or `FAIL` if there is none.

#### Method Next: next valid integer list

- `Next(integer list p, constraints)`

- Returns the integer list following `p` satisfying `constraints` or `FAIL` if there is none.

#### Example 1

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 ]

#### Example 2

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)

#### Background

- Except for one degenerate case where the algorithm may run forever without producing anything (see example 2), the complexity of the generation algorithm is constant time amortized for each integer list produced.

- The generation algorithm could be extended to deal with non-constant slope constraints and with negative parts, as well as to accept a range parameter instead of a single integer for the sum `n` of the lists. Let us know if those would be useful features.

- Counting is done by brute force generation.

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package