[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:

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

Details

Entries

domtype

The MuPAD domain used to represent integer lists: DOM_LIST

Method count: number of valid integer lists

Method generator: generator for valid integer lists

Method list: list of the valid integer lists

Method first: first valid integer list

Method Next: next valid integer list

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

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package