combinat::decomposableObjects – decomposable combinatorial objects

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

→ Examples

Creating the Type

combinat::decomposableObjects(specification, <Options>)

Parameters:

Options:

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); one can also specify weights for atoms and epsilons; see the example 8 for details;

  • Z:this is equivalent to Atom(Z), and is provided as a syntactic sugar;

  • Predefined(countrandomunrank):a class described by the functions count, random, unrank;

  • Domain(class) or class: a combinatorial 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, ...

  • BoxedProd(A, B, ...): (for labelled structures) similar to Prod, but forces the smallest label to be on the A side.

  • Sequence(A): all sequences of elements of A; A should not contain elements of size zero

  • Multiset(A): all sets of elements of A with repetitions; A should not contain elements of size zero

  • Powerset(A): all sets of elements of A without repetitions; A should not contain elements of size zero      

  • Cycle(A): all directed cycles of elements of A, including the empty cycle; A should not contain elements of size zero    

  • Alias(A), Alias(A,f): an alias to the class A, or the image of the class A by the function f.

  The constructor Sequence as well as, in the labelled case, the constructors Powerset, Multiset, and Cycle accept further options MinLength, MaxLength, and Length to set length restrictions: for example, Sequence(A, MinLength=3, MaxLength=5) represents all the sequences of elements of A of length between 3 and 5.

• 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':

• Labelling type = 'unlabelled':

• Note: some of the unlabelled 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 of course only do counting if the provided domain class can, and similar wise for random, unrank, ...

Superdomain

Dom::BaseDomain

Categories

Cat::CombinatorialClass

Axioms

Ax::systemRep

count – number of decomposable objects

(combinat::decomposableObjects(specification, <Options>))::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 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 . This is only possible for context free specifications. Also, for very large specifications (say more than 100 non terminals), the precomputation can become quite expensive; if one is only interested in counting for small values of (say ), it may be preferable to stick to Naive or Lazy products.

generator – generator for decomposable objects

(combinat::decomposableObjects(specification, <Options>))::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.

list – list of decomposable objects

(combinat::decomposableObjects(specification, <Options>))::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.

unrank – unranking of decomposable objects

(combinat::decomposableObjects(specification, <Options>))::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 with the Boustrophedonic order, and otherwise.

random – random object

(combinat::decomposableObjects(specification, <Options>))::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 with the Boustrophedonic order, and otherwise.

standardSpecification – specification in standard form

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

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

standardSpecificationCount – specification in standard form

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

Returns a simplified form of the specification in standard form which is equivalent for counting purposes.

This is done by sorting the operands of Prod and Union (the operations + and * on generating series are commutative!), erasing the names of the singletons and atoms and assigning them with a default weight if they do not have one yet. Then, the productions that are identical are factored out using Alias. Further optimizations would be possible; in particular, productions that are recursively equivalent are not detected yet.

algebraicEquation – algebraic equation for the generating series

(combinat::decomposableObjects(specification, <Options>))::algebraicEquation(<{A}>)

Returns an algebraic equation satisfied by the generating series for the non terminal A.

Computing this algebraic equation is only possible if the specification is context free; FAIL is returned if this is not the case.

recurrenceRelation – recurrence relation for the coefficients of the generating series

(combinat::decomposableObjects(specification, <Options>))::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.

generateCode – automatic C code generation

(combinat::decomposableObjects(specification, <Options>))::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 MuPAD with 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 restrictions on the specifications that the C program can manage, 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 , and memory complexity , not taking into account the coefficient growth. As for the "count" method, this could be reduced to for context free grammars and to otherwise. The random generation algorithm is of complexity . 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:

Example 2:

Example 3:

Example 4:

Example 5:

Example 6:

Example 7:

Example 8:

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 reasonable algorithm: this includes mainly unranking and uniform random generation of unlabelled Cycles, as well as random generation of labelled Powerset(A) without knowing how to unrank elements of A. Beware that the currently implemented random generation of unlabelled Cycles is not uniform; furthermore, randomly generated unlabelled Cycles and Sets are not normalized!

• In most cases however, the functionalities are just not yet implemented. This library could also be extended and generalized in many other ways. Please contact the authors if you need some 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 of a product Prod(A,B) are built from objects of A of size and objects of B of size , for in . The Boustrophedonic option controls in which order runs through . If it is set to false, the straightforward order is used. Otherwise, the somewhat less natural order is used; it happens that this reduces the worst case complexity of the unranking and random generation operations from to !

• This library originates 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.