[Previous] [Next] [Contents]

## `Cat::CombinatorialClass` -- the category of combinatorial classes

#### Introduction

`Cat::CombinatorialClass` represents the category of combinatorial classes that is the categories of sets that can be enumerated, counted...

#### Generating the category

`Cat::CombinatorialClass()`

#### Categories

`Cat::BaseCategory`

#### Details

- A combinatorial class is a set of ``objects'' sharing a same combinatorial property, for example the set of binary trees, the set of integer partitions, ...This has to be understood as a rough definition because there is no strict formalization of what is a combinatorial class.

- Each object of a combinatorial class is supposed to have a ``size'' which is most of the time an integer, for example the number of node of a tree (see `combinat::trees`), but can be anything else, for example the size of a vector of nonnegative integers (see `combinat::integerVectors`) is a pair of integers: its sum and its length.

- The purpose of the category `Cat::CombinatorialClass` is to ensure that all combinatorial classes share a common interface. `Cat::CombinatorialClass`also provide default implementations when there is no better algorithm. For example, if you don't known how to count a set of combinatorial ``objects'', count is done by expanding the list, which can be very inefficient.

- To define a proper combinatorial class `cl`, the domain `cl` must at least define the methods `cl::isA`, and one of the following combinations of methods, the other are provided by defaults:
  - `cl::list`;
  - `cl::generator`;
  - `cl::first` and `cl::Next`;
  - `cl::last` and `cl::previous`;
  - `cl::unrank`.
  Note that these default implementations can be very inefficient in time or space compared to ad-hoc implementations.

- In a near future we plan to write some class to manipulate other classes (for example a subclass of a class). To this end, it is very important that the functions `isA`, `list`, `generator` take the very same argument.

#### Basic Entries

type

The MuPAD type of the object belonging to the class. Note that if `cl` is a combinatorial class it is sufficient to call `testtype(obj, cl)` to test the type of a object.

domtype

The MuPAD domain of the object belonging to the class. Since a combinatorial class can be a facade domain, it can be different from `"type"`.

interfaceCombinatorialClass

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

#### Method isA: test if an object is an element of the class.

- `isA(object x, <, size s, constraints c>)`

- Check if an object belongs to the combinatorial class. Moreover if optional `s` or `c` are given, it check if the object verify the constraints. An domains that belongs to `Cat::CombinatorialClass` should define `"isA"` rather that `"type"` and `"testtype"`. Hence, these two functions does not accept extra constraints and are provided by default by `Cat::CombinatorialClass`. This methods is mandatory.

#### Method size: size of an object.

- `size(object x)`

- Returns the size of an object of the class.

#### Method count: count the number of objects.

- `count( <size s, constraints c>)`

- Returns the number of objects of the class. If the class is infinite then `s` must be given. In this case `"count"` returns the number of objects of the class of the size `s`. Moreover, if `c` is given, returns the number of objects of the class of the size `s` satisfying the extra constraints `c`.

#### Method list: list of the objects

- `list( <size s, constraints c>)`

- Returns the list of objects of the class. If the class is infinite then `s` must be given. In this case `"count"` returns the number of objects of the class of the size `s`. Moreover, if `c` is given, returns the list of objects of the class of the size `s` satisfying the extra constraints `c`.

- If `cl` is a combinatorial class, the call `cl(size)` is a shortcut for `cl::list(size)`. Note that this shortcut should be reserved at the interactive level an not during programming.

#### Method generator: generator for the objects

- `generator( <size s, constraints c>)`

- Returns a generator for the objects of the class. If `s` or `c` is given, returns the a generator for the objects of the class of the size `s` satisfying the extra constraints `c`.

- If to write a class `cl` you need a default implementation for `cl::generator`, you can use one of the following which are provided by `Cat::CombinatorialClass`:
  - `cl::generatorFromList` using `cl::list`;
  - `cl::generatorFromNext` using `cl::first` and `cl::Next`;
  - `cl::generatorFromPrevious` using `cl::last` and `cl::previous`;
  - `cl::generatorFromUnrank` using `cl::unrank`;

#### Method first: first objects

- `first( <size s, constraints c>)`

- Returns the first object of the class. If `s` or `c` is given, returns the first object of the class of the size `s` satisfying the extra constraints `c`.

#### Method last: last object

- `last( <size s, constraints c>)`

- Returns the last object of the class. If `s` or `c` is given, returns the last object of the class of the size `s` satisfying the extra constraints `c`.

#### Method Next: next object

- `Next(object o, <size s, constraints c>)`

- Returns the next object of the class. If `s` or `c` is given, returns the next object of the class of the size `s` satisfying the extra constraints `c`.

#### Method previous: previous object

- `previous(object o, <size s, constraints c>)`

- Returns the previous object of the class. If `s` or `c` is given, returns the previous object of the class of the size `s` satisfying the extra constraints `c`.

#### Method rank: rank object

- `rank(object o, <size s, constraints c>)`

- Returns the rank of the object `o` in the list of the object belonging to class. If `s` or `c` is given, returns the rank of the object `o` in the list of the object of the class of the size `s` satisfying the extra constraints `c`.

#### Method unrank: unrank object

- `unrank(number n, <size s, constraints c>)`

- Returns the `n`-th object of the class. If `s` or `c` is given, returns the `n`-th object of the class of the size `s` satisfying the extra constraints `c`.

#### Method random: random object

- `random( <size s, constraints c>)`

- Returns a random object of the class. If `s` or `c` is given, returns a random object of the class of the size `s` satisfying the extra constraints `c`.

#### Method _less: comparison of two objects

- `_less( <object o1, object o2>)`

- Where it makes sense, compare the object `o1` and `o2` and returns true if `o1` is smaller than `o2`.

#### Method generatingSeries: the generating series of the class.

- `generatingSeries( <variable z>)`

- The generating series of a class C is defined as f_C(z) := ∑_x ∈C z^size(x) = ∑_n #{objects of C of size n} z^n . Thus the coefficient of xn in the generating series fC(z) is the number of object of size n. When known `"generatingSeries"` return an expression for the generating series.

#### Details

- To help the writing of combinatorial classes, the following methods are provided. They are not supposed to be called directly, they are here rather to provide default implementations by using other methods.

  Note that these default implementations can be very inefficient in time or space compared to ad-hoc implementations.

#### Method countFromGenerator: count the number of objects using generation.

- `countFromGenerator( <size s, constraints c>)`

- Returns the number of objects of the class. The counting is done by generating all the objects step by step.

  This is the default implementation for the count methods if nothing is provided.

#### Method listFromGenerator: list the number of objects using generation.

- `listFromGenerator( <size s, constraints c>)`

- Returns the list of objects of the class. This is done by generating all the objects step by step, using a size-doubling arrays to avoid reallocating the list at each step.

  This is the default implementation for the list methods if nothing is provided.

#### Details

- The following methods are defaults implementations for `"generator"`. The categories `Cat::CombinatorialClass` try in the following order to use these implementations when the necessary functions are defined:
  - `"generatorFromNext"` if `"first"` and `"Next"` are defined;
  - `"generatorFromPrevious"` if `"last"` and `"previous"` are defined;
  - `"generatorFromUnrank"` if `"Unrank"` is defined;
  - `"generatorFromList"` if `"list"` is defined
- If no implementation is possible because the necessary methods are not provided, an error is raised at the first call of generator.

#### Method generatorFromNext: generator for the objects using `"first"` and `"Next"`

- `generatorFromNext( <size s, constraints c>)`

- Returns a generator for the objects of the class. This is done by calling `"Next"` at each step, which is most of the time a relatively good implementations with respect to time and space.

  This is the default implementation for the generator methods if `"first"` and `"Next"` are provided.

#### Method generatorFromPrevious: generator for the objects using `"last"` and `"previous"`

- `generatorFromPrevious( <size s, constraints c>)`

- Returns a generator for the objects of the class. This is done by calling `"previous"` at each step, which is most of the time a relatively good implementations with respect to time and space.

#### Method generatorFromUnrank: generator for the objects using `"unrank"`

- `generatorFromUnrank( <size s, constraints c>)`

- Returns a generator for the objects of the class. This is done by calling `"unrank"` at each step, which is most of the time a relatively good implementations with respect to time and space.

#### Method generatorFromList: generator for the objects using `"list"`

- `generatorFromList( <size s, constraints c>)`

- Returns a generator for the objects of the class. This is done by expanding the list when the generator is constructed.

  This is the fallback implementation of generator if noting better is possible. This is very inefficient with respect to memory space.

#### Example 1

Suppose that you want to define the combinatorial class of the binary vectors. The size is the length of the vector. It is easy to write a `"Next"` function, by thinking that a vector is a binary expansion of a number. This is done by searching the first 0 and replacing the initial sequence 11...10 by 00...01. Here is a way to do this:

    >> nextBinExp := proc(lst)
               local pos;
           begin
              if (pos := contains(lst, 0)) <> 0 then
                  [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
              else FAIL
              end_if;
           end:
           nextBinExp([1, 1, 0, 1, 0, 1, 1, 0]);

                             [0, 0, 1, 1, 0, 1, 1, 0]

Here is the way to use that to build a combinatorial class. We have to define `"isA"` for the type checking and `"first"`, `"Next"` for generation :

    >> domain zeroOneVectors
           inherits Dom::BaseDomain;
           category Cat::CombinatorialClass;
           axiom    Ax::systemRep;

           isA := // Type checking.
           proc(obj         : Type::AnyType,
               size = FAIL : Type::Union(Type::NonNegInt, DOM_FAIL)) : DOM_BOOL
           begin
               if domtype(obj) <> DOM_LIST then return(FALSE); end_if;
               if {op(obj)} minus {0,1} <> {} then return(FALSE); end_if;
               if args(0) = 1 then return(TRUE);
               else
                   bool(nops(obj) = size);
               end_if;
           end_proc;

           size  := proc(v : dom) : Type::NonNegInt begin nops(v); end_proc;

           first := proc(size : Type::NonNegInt) : dom
                    begin
                        [ 0 $ size ];
                    end_proc;

           Next := proc(lst : dom) : Type::Union(DOM_FAIL, dom)
                       local pos;
                   begin
                       if (pos := contains(lst, 0)) <> 0 then
                           [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
                       else FAIL
                       end_if;
                   end_proc;
       end_domain:

The type Checking is working:

    >> testtype([1, 0, 1], zeroOneVectors);
       testtype([1, 0, 2], zeroOneVectors)

                                       TRUE

                                       FALSE

The method `"list"` and is provided by `Cat::CombinatorialClass`

    >> zeroOneVectors::list(3)

          [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],

             [1, 0, 1], [0, 1, 1], [1, 1, 1]]

Together with the method `"generator"`:

    >> (g := zeroOneVectors::generator(2);
       g(), g(), g(), g(), g())

                       [0, 0], [1, 0], [0, 1], [1, 1], FAIL

The following useful shortcut is also defined

    >> zeroOneVectors(3)

          [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],

             [1, 0, 1], [0, 1, 1], [1, 1, 1]]

A default implementation is provided for the `"count"` method:

    >> zeroOneVectors::count(4)

                                        16

However, it is very slow, since it simply generates all the elements, and count them:

    >> zeroOneVectors::count(10);
       time(zeroOneVectors::count(10))

                                       1024

                                       240

Whenever possible, it is better to implement the `"count"` method:

    >> zeroOneVectors::count := i -> 2^i:
       zeroOneVectors::count(10);
       time(zeroOneVectors::count(10))

                                       1024

                                         0

#### Changes

- `Cat::CombinatorialClass` is a new category

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package