combinat::decomposableObjects
--
decomposable combinatorial objects
The library
provides functions
for counting, generating, and drawing at random the decomposable
combinatorial objects defined recursively by
combinat::decomposableObjects
(specification)specification
.
combinat::decomposableObjects(specification <, Options>)
specification | - | A combinatorial specification |
Labelled = | - | Selects between labeled or unlabeled combinatorial objects.
b must be TRUE or FALSE . The default value is
FALSE . |
Products = | - | 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 = | - | 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 = | - | 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 . |
Epsilon(A)
:A
; as a syntactic sugar, a production of
the form A = Epsilon
is rewritten into A = Epsilon(A)
;
Atom(A)
:A
; as a syntactic sugar, a production of the form
A = Atom
is rewritten into A = Atom(A)
;
Z
:Atom(Z)
, and is provided as a
syntactic sugar;
Predefined(count <, random> <, unrank>)
:count
, random
,
unrank
;
Domain(class)
:class
(see
Cat::CombinatorialClass
).
Union(A, B, ...)
:Prod(A, B, ...)
:Multiset(A)
:Powerset(A)
:Sequence(A)
:Cycle(A)
:Alias(A)
, Alias(A,f)
: an alias to the class
A
, or the image of the class A
by the function
f
.
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 = <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.
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.Domain(class)
, the system can
only do counting if the provided domain class
can, and
similar wise for random
, unrank
, ...Cat::CombinatorialClass
count(nonnegative integer n <, A>)
n
derived by the
non terminal A
in the specification.A
is the main non terminal.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
).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.
generator(nonnegative integer n <, A>)
n
derived by
the non terminal A
in the specification.A
is the main non terminal."unrank"
, and only
works for context free grammars.
list(nonnegative integer n <, A>)
n
derived by
the non terminal A
in the specification.A
is the main non terminal."unrank"
, and only
works for context free grammars.
unrank(nonnegative integer i, nonnegative integer n <, A>)
n
derived by the non
terminal A
in the specification.A
is the main non terminal.
random(nonnegative integer n <, A>)
n
derived by
the non terminal A
in the specification.A
is the main non terminal.
standardSpecification()
standardSpecificationCount()
recurrenceRelation( <A
> <, identifier u> <,
identifier u>)
A
.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
. FAIL
is returned if this is
not the case.
generateCode(string filename)
filename
which
can be used for efficient counting and random generation of
objects.filename
is blah.c,
here is the command line for the gcc compiler:
gcc blah.c -lgmp -o blah.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.Alias
. An error is raised
if this is the case."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. 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))]
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)
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
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
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
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"]
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.
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)! 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.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.Ax::systemRep
combinat::decomposableObjects
is a new library
MuPAD Combinat, an open source algebraic combinatorics package