[Previous] [Next] [Contents]

## `combinat::decomposableObjects` -- decomposable combinatorial objects

#### Introduction

The library ``combinat::decomposableObjects`(specification)` provides functions for counting, generating, and drawing at random the decomposable combinatorial objects defined recursively by `specification`.

#### Domain

`combinat::decomposableObjects(specification <, Options>)`

#### Parameters

`specification` | - | A combinatorial specification

#### Options

`Labelled = `b`` | -

| Selects between labeled or unlabeled combinatorial objects. `b` must be `TRUE` or `FALSE`. The default value is `FALSE`.

`Products = `Type`` | -

| Choose the counting algorithm. `Type` is one of `Naive`, `Holonomic`. The default value is `Holonomic` for context free grammars, and `Naive` otherwise. See `"count"` for details.

`MainNonTerminal = `A`` | -

| Specifies the main non terminal of the specification. `A` must be a non terminal appearing in the specification. By default, the first one (as returned by `op(specification,[1,1])` is used). This option used to be incorrectly named `MainTerminal`.

`Boustrophedonic = `b`` | -

| Specifies the order in which elements of products are generated; see ``background'' section for more details. `b` must be `TRUE` or `FALSE`. The default value is `TRUE`.

#### Details

- A decomposable combinatorial class is recursively built from basic classes using constructors. The basic classes are:
  - Epsilon or `Epsilon(A)`:
    a class containing a single object of size zero, named Epsilon or `A`; as a syntactic sugar, a production of the form `A = Epsilon` is rewritten into `A = Epsilon(A)`;
  - Atom or `Atom(A)`:
    a class containing a single object of size one, named Atom or `A`; as a syntactic sugar, a production of the form `A = Atom` is rewritten into `A = Atom(A)`;
  - `Z`:
    this is equivalent to `Atom(Z)`, and is provided as a syntactic sugar;
  - `Predefined(count <, random> <, unrank>)`:
    a class described by the functions `count`, `random`, `unrank`;
  - `Domain(class)`:
    a class represented by the MuPAD domain `class` (see `Cat::CombinatorialClass`).
  The available constructors are:
  - `Union(A, B, ...)`:
    the disjoint union of the classes A, B, ...
  - `Prod(A, B, ...)`:
    the partitional product of the classes A, B, ...
  - `Multiset(A)`:
    all sets with repetitions whose elements are in A
  - `Powerset(A)`:
    all sets without repetitions whose elements are in A.
  - `Sequence(A)`:
    all sequences of elements of A
  - `Cycle(A)`:
    all directed cycles of elements of A, including the empty cycle
  - `Alias(A)`, `Alias(A,f)`: an alias to the class `A`, or the image of the class `A` by the function `f`.
  For the constructor `Sequence`, it is possible to add some restrictions on the cardinality with the `MinLength`, `MaxLength` and `Length` options: for example, `Sequence(A,MinLength=3)` represents all the sequences of elements of `A` of length at least 3. Similar restrictions could be added for sets and cycles, but are not yet implemented.

- A combinatorial specification is a list (or set or table) of productions of the form `A = <rhs>`, where `A` is the name of the class being defined, and `<rhs>` is an expression involving elementary classes, constructors and other classes. `A` is called a non terminal. For example, below are the specifications of some well-known combinatorial classes:

  Labelling type = 'labelled':

  `[A = Prod(Z,Powerset(A))]` | non plane trees
  `[B = Union(Z,Prod(B,B))]` | plane binary trees
  `[C = Prod(Z,Sequence(C))]` | plane general trees
  `[D = Powerset(Cycle(Z))]` | permutations in cycle notation
  `[E = Powerset(Cycle(A)), A=Prod(Z,Powerset(A))]` | functional graphs
  `[F = Powerset(Powerset(Z,MinLength=1))]` | set partitions
  `[G = Union(Z,Prod(Z,Powerset(G,Length=3)))]` | non plane ternary trees
  `[H = Union(Z,Powerset(H,MinLength=2))]` | hierarchies
  `[L = Powerset(Powerset(Powerset(Z,MinLength=1),MinLength=1))]` | 3-balanced hierarchies
  `[M = Sequence(Powerset(Z,MinLength=1))]` | surjections

  Labelling type = 'unlabelled':

  `[A = Powerset(Sequence(Z,MinLength=1))]` | integer partitions
  `[B = Sequence(Union(Z,Z))]` | binary sequences
  `[C = Cycle(Powerset(Z,MinLength=1))]` | necklaces
  `[D = Prod(Z,Powerset(D))]` | rooted unlabelled trees
  `[E = Powerset(Cycle(D)), D=Prod(Z,Powerset(D))]` | random mappings patterns
  `[F = Union(Z,Powerset(F,Length=2))]` | nonplane binary trees
  `[G = Union(Z,Powerset(G,Length=3))]` | nonplane ternary trees
  `[H = Union(Z,Powerset(H,MinLength=2))]` | unlabelled hierarchies

  Note: some of the specifications above require not yet implemented features.

- A specification is context free if it only uses the constructors `Prod` and `Union`, and those derived from them like `Sequence`. In particular this excludes the `Powerset`, `Multiset`, and `Cycle` constructions. Some features of this library are only available for context free specifications.

- When the specification uses `Domain(class)`, the system can only do counting if the provided domain `class` can, and similar wise for `random`, `unrank`, ...

- Known bug for labelled objects: they are currently generated and returned without their labels!

#### Categories

`Cat::CombinatorialClass`

#### Method count: number of decomposable objects

- `count(nonnegative integer n <, A>)`

- Returns the number of objects of size `n` derived by the non terminal `A` in the specification.
- By default, `A` is the main non terminal.
- If Products is set to `Naive`, the counting is done by naive products of generating series; this gives a O(n2) complexity (not counting the coefficient growth). Those products could be done using a lazy Karatsuba-type algorithm with a complexity of `O(n^3/2)`; however this is currently only partly implemented (Products will be `Lazy`).
- If Products is set to `Holonomic`, the system will first precompute a linear recurrence between the coefficients of the generating series (see `"recurrenceRelation"`), and then use it for the counting; this gives a complexity of O(n); however this is only possible for context free specifications.

#### Method generator: generator for decomposable objects

- `generator(nonnegative integer n <, A>)`

- Returns a generator for the objects of size `n` derived by the non terminal `A` in the specification.
- By default, `A` is the main non terminal.
- Currently, this method is based on `"unrank"`, and only works for context free grammars.

#### Method list: list of decomposable objects

- `list(nonnegative integer n <, A>)`

- Returns the list of the objects of size `n` derived by the non terminal `A` in the specification.
- By default, `A` is the main non terminal.
- Currently, this method is based on `"unrank"`, and only works for context free grammars.

#### Method unrank: unranking of decomposable object

- `unrank(nonnegative integer i, nonnegative integer n <, A>)`

- Returns the i-th object of size `n` derived by the non terminal `A` in the specification.
- By default, `A` is the main non terminal.
- Currently, this method only works for context free grammars; algorithm do exists for the other constructions, but are not yet implemented.
- The worst case complexity is O(n log n) with the Boustrophedonic order, and O(n2) otherwise.

#### Method random: random object

- `random(nonnegative integer n <, A>)`

- Returns a random object of size `n` derived by the non terminal `A` in the specification.
- By default, `A` is the main non terminal.
- The worst case complexity is O(n log n) with the Boustrophedonic order, and O(n2) otherwise.

#### Method standardSpecification: specification in standard form

- `standardSpecification()`

- Returns the standard form of the specification; this is an equivalent specification which uses only the constructors Atom, Union, Prod, Theta, Int, and Delta. Theta is the pointing constructor, Int the formal inverse of Theta, and Delta is the generalized diagonal.

#### Method standardSpecificationCount: specification in standard form

- `standardSpecificationCount()`

- Returns a simplified form of the specification in standard form which is equivalent for counting purposes.
- This is done by erasing the names of the singletons and atoms, sorting the operands of Prod and Union (the operations + and * on generating series are commutative!), and factoring out the productions that are identical using Alias. Further optimizations would be possible; in particular, productions that are recursively equivalent are not detected yet.

#### Method recurrenceRelation: recurrence relation for the coefficients of the generating series

- `recurrenceRelation( <`A`> <, identifier u> <, identifier u>)`

- Returns a recurrence relation between the coefficients of the generating series for the non terminal `A`.
- The recurrence relation is given in the form of an expression such as `u(n) - n*u(n-1) - u(n-2)`, it means that the number of objects of size `n` is equal to `n` times the number of objects of size `n-1` plus the number of objects of size `n-2`.
- Computing the recurrence relation is only possible if the specification is context free; `FAIL` is returned if this is not the case.

#### Method generateCode: automatic C code generation

- `generateCode(string filename)`

- Generate a `C` program in the file `filename` which can be used for efficient counting and random generation of objects.
- To compile the program, the `GMP` library version 4.0 or higher is required; aside from this, any `C` compiler should work. Admitting that `filename` is `blah.c`, here is the command line for the `gcc` compiler: `gcc blah.c -lgmp -o blah`.
- Once compiled, the program can be used completely independently from MuPADwith the command: `blah n [k seed]`. This writes to the standard output `k` random objects of size `n` (or `FAIL` if no object of size `n` exists), one per line. If `k` is `0`, then the number of objects of size `n` is output instead. A third parameter `seed` can be provided to initialize the `GMP` random generator.
- There are some restrictions on the specifications, in particular for complicated use of `Alias`. An error is raised if this is the case.
- Currently the counting algorithm uses naive multiplication of generating series and whose time complexity is O(n2), and memory complexity O(n), not taking into account the coefficient growth. As for the `"count"` method, this could be reduced to O(n) for context free grammars and to O(n3/2) otherwise. The random generation algorithm is of complexity n log (n). For quasi-uniform random purpose, the counting could be done with floating point numbers (or better interval arithmetic), to ensure constant time arithmetic operations.

#### Example 1

We create a domain for complete binary trees:

    >> BinaryNaive:=combinat::decomposableObjects({B=Union(Z,Prod(B,B))}):

Standard form of specification

    >> BinaryNaive::standardSpecification()

                           table(
                             Z = Atom(Z),
                             B = Union(Z, NonTerminal1),
                             NonTerminal1 = Prod(B, B)
                           )

The number of binary tree of size 0 to 10

    >> BinaryNaive::count(i) $i=0..10

                    0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

A random tree of size 1 and size 2

    >> BinaryNaive::random(i)$ i=1..2

                                   Z, Prod(Z, Z)

List of all objects of size 4 satisfying the specification

    >> BinaryNaive::list(4)

          [Prod(Z, Prod(Z, Prod(Z, Z))), Prod(Z, Prod(Prod(Z, Z), Z)),

             Prod(Prod(Z, Prod(Z, Z)), Z), Prod(Prod(Prod(Z, Z), Z), Z),

             Prod(Prod(Z, Z), Prod(Z, Z))]

#### Example 2

This specification is the Schroeder tree with Naive product:

    >> SchroederNaive:=combinat::decomposableObjects(
       {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):

Standard form of specification

    >> SchroederNaive::standardSpecification()

                    table(
                      Z = Atom(Z),
                      B = Union(Z, NonTerminal1, NonTerminal4),
                      NonTerminal4 = Prod(Z, NonTerminal3),
                      NonTerminal3 = Alias(NonTerminal2, op),
                      NonTerminal2 = Prod(B, B),
                      NonTerminal1 = Prod(Z, B)
                    )

The number of Schroeder tree of size 0 to 10

    >> SchroederNaive::count(i) $i=0..10

                      0, 1, 1, 2, 4, 9, 21, 51, 127, 323, 835

A random tree of size 1 and size 2

    >> SchroederNaive::random(i)$ i=1..2

                                   Z, Prod(Z, Z)

#### Example 3

This specification defines the Schroeder trees with Naive and Holonomic product:

    >> SchroederHolonomic:=combinat::decomposableObjects(
       {B=Union(Z,Prod(Z,B),Prod(Z,B,B))},Products=Holonomic):
       SchroederNaive:=combinat::decomposableObjects(
       {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):

Time necessary to count the number of Schroeder tree of size 500 according to whether you use the holonomic products or not

    >> time(SchroederNaive::count(500));time(SchroederHolonomic::count(500));

                                        11340

                                        30

Time necessary to generate a random Schroeder tree of size 500 according to whether you use holonomic products or not

    >> time(SchroederNaive::random(500));
       time(SchroederHolonomic::random(500));

                                        820

                                        490

#### Example 4

We demonstrate how to use the functions generator and list.

    >> Shroeder:=combinat::decomposableObjects(
       {B=Union(Z,Prod(Z,B),Prod(Z,B,B))}):

    >> Shroeder::count(5)

                                         9

All objects of size 5 satisfying the specification

    >> Shroeder::list(5)

          [Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),

             Prod(Z, Prod(Z, Prod(Z, Z, Z))),

             Prod(Z, Prod(Z, Z, Prod(Z, Z))),

             Prod(Z, Prod(Z, Prod(Z, Z), Z)),

             Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),

             Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),

             Prod(Z, Prod(Z, Z), Prod(Z, Z))]

We build and use a generator for those objects:

    >> f:=Shroeder::generator(5):

    >> f() $ i =0..9

          Prod(Z, Prod(Z, Prod(Z, Prod(Z, Z)))),

             Prod(Z, Prod(Z, Prod(Z, Z, Z))),

             Prod(Z, Prod(Z, Z, Prod(Z, Z))),

             Prod(Z, Prod(Z, Prod(Z, Z), Z)),

             Prod(Z, Z, Prod(Z, Prod(Z, Z))), Prod(Z, Z, Prod(Z, Z, Z)),

             Prod(Z, Prod(Z, Prod(Z, Z)), Z), Prod(Z, Prod(Z, Z, Z), Z),

             Prod(Z, Prod(Z, Z), Prod(Z, Z)), FAIL

#### Example 5

We create a domain for labeled and unlabeled complete binary trees:

    >> BinaryUnlabeled:=combinat::decomposableObjects(
       {B=Union(Z,Prod(B,B))},Labelled=FALSE):
       BinaryLabeled:=combinat::decomposableObjects(
       {B=Union(Z,Prod(B,B))},Labelled=TRUE):

Number of objects of size 0 to 10 satisfying the specification

    >> BinaryUnlabeled::count(i)$i=0..10;
       BinaryLabeled::count(i)$i=0..10;

                    0, 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

          0, 1, 2, 12, 120, 1680, 30240, 665280, 17297280, 518918400,

             17643225600

#### Example 6

We use the mechanics of `combinat::decomposableObjects` to present the classical and striking ``balls and bars'' model for integer compositions. A composition like `[2,1,3]` can be represented as a string of balls and bars by using sequences of balls, separated by bars, here: `öoIoIooo"`. Such strings can be described by the grammar BB = Union(o, oBB, oIBB).

    >> ballsAndBars :=
       combinat::decomposableObjects(
          [
           Ball         = Atom("o"),
           Bar          = Epsilon("I"),
           BB           = Union(Ball,
                                Alias(Prod(Ball, BB),op),
                                Alias(Prod(Ball, Bar, BB),op)
                               ),
           BallsAndBars = Alias(BB, _concat)
          ], MainNonTerminal = BallsAndBars):

There are 2n-1 balls and bars strings with n balls:

    >> ballsAndBars::count(i) $ i = 1..10

                       1, 2, 4, 8, 16, 32, 64, 128, 256, 512

This can be seen directly from the recurrence relation:

    >> ballsAndBars::recurrenceRelation()

                                 2 u(n - 1) - u(n)

Here are all the compositions of 3:

    >> ballsAndBars::list(3)

                         ["ooo", "ooIo", "oIoo", "oIoIo"]

#### Background

- Not all functionalities (`count`, `random`, `unrank`, `generator`, `list`) are available for all constructors; some restrictions are documented above; otherwise, the system should emit an error if such a non available functionality is called.

  In some cases, there is no known algorithm; in most cases, the functionalities are just not yet implemented. Please contact the authors if you need missing functionalities for your applications. Help would also be very welcome.

- The Boustrophedonic option specifies the order in which elements of products are generated. To be specific, the objects of size n of a product `Prod(A,B)` are built from objects of `A` of size k and objects of `B` of size n-k, for k in {1,...,n}. The Boustrophedonic option controls in which order k runs through {1,...,n}. If it is set to false, the straightforward order k=1..n is used. Otherwise, the somewhat less natural order k=1,n,2,n-2,... is used; it happens that this reduces the worst case complexity of the unranking and random generation operations from O(n2) to O(nlog n)!

- It would be relatively straightforward to do weighted enumeration, where atoms and epsilons would keep their respective sizes 1 and 0, but could be assigned weights in any ring `R`. A simple application is to use 1.0 and 0.0 as weights, so as to do approximate counting in floating point arithmetic. A further possible extension would be to allow the constructors to apply any transformation on the weights of their operands. A typical application is to compute the generating series of binary trees of size 10 with respect to their maximal depth.

- This library has been adapted from the `CS` library for MuPAD 1.4 from Sylvie Corteel, Alain Denise, Isabelle Dutour, Frédéric Sarron and Paul Zimmermann. Parts of the documentation come from the `GAIA` package (ancestor of `combstruct`) by Paul Zimmermann.

- References:
  - Flajolet, Philippe and Zimmermann, Paul and Van Cutsem, Bernard, A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, 1994, 132, 1-2, pp. 1-35.
  - Denise, Alain and Dutour, Isabelle and Zimmermann, Paul, CS: a MuPAD package for Counting and Randomly Generating Combinatorial Structures, Proceedings of FPSAC'98, 1998, pp. 195-204.
  - Conrado Martinez and Xavier Molinero, Generic Algorithm for the Generation of Combinatorial Objects, 2003.

- The specifications used by this library are in good parts compatible with those from the `combstruct` package for `Maple`. There are some differences though, in order to ensure the coherence with the rest of the MuPAD library: the constructor names `Powerset` and `Multiset` are used instead of respectively `PowerSet` and `Set`; furthermore, cardinality restrictions are stated as `MinLength=3` instead of `card>=3`; finally, the `Cycle` construction includes the empty cycle. If needed, it would be straightforward to write a converter.

#### Super-Domain

`Dom::BaseDomain`

#### Axioms

`Ax::systemRep`

#### Changes

- `combinat::decomposableObjects` is a new library

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package