is defined as Cat::CombinatorialClass – the category of combinatorial classes
Cat::CombinatorialClass represents the category of combinatorial classes, that is, the category of sets that can be enumerated, counted, …
Categories
Details:
A combinatorial class is a set of “objects” sharing some combinatorial property that one wants to count, enumerate, generate at random, etc. Typical combinatorial classes are the set of binary trees (see combinat::binaryTrees) or the set of integer partitions (see combinat::partitions). This has to be understood as a rough definition because there is no strict formalization of what a combinatorial class is.
Each object of a combinatorial class is supposed to have a “size” which most of the time is an integer, for example the number of nodes of a tree (see combinat::trees), but it 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, which consists mainly in the methods isA for type testing, and count, list and generator for counting, listing, and generating objects of a given size.
Cat::CombinatorialClass also provides some default implementations, which can be overridden when there is a better algorithm. For example, if you don't known how to count a set of combinatorial “objects”, count is implemented 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 in this category via default implementations:
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.
There are domains that manipulate combinatorial classes, as for example combinat::subClass to build a subclass of a class or Dom::FreeModulePoly(R, Basis), where R is a ring and Basis is a combinatorial class. To this end, it is very important that the functions isA, count, list, generator take their arguments in a uniform way.
Entries
|
"domtype" |
The MuPAD domain of the object belonging to the class. Since a combinatorial class can be a façade domain, it can be different from dom. |
Basic Methods
isA – membership testing
Cat::CombinatorialClass::isA(x, <size s, constraints c>)
Checks if the object x belongs to the combinatorial class. If optional s or c are given, checks further if x has size s and satisfies the constraints.
Apart from sequences, any MuPAD object x shall be accepted as input. On the other hand isA is allowed to raise type errors about the size and constraints.
The return value is a boolean (DOM_BOOL). TRUE and FALSE shall be guaranted answers. In case the membership testing is too costly (if not infeasible), isA may return the MuPAD value UNKNOWN. The default implementation is to always return UNKNOWN.
This function plays a role which is closely related to the testtype mechanism. However it is more general, because of the optional size and constraints arguments, and because an UNKNOWN answer is allowed. Cat::CombinatorialClass provides a default implementation of testtype which uses isA. An UNKNOWN answer is then translated into TRUE; indeed, the most common use case is type checking of arguments: there, when we can't decide whether an input argument, we want to accept it.
size – size of an object
Cat::CombinatorialClass::size(dom x)
Returns the size of an object of the class.
count – number of objects
Cat::CombinatorialClass::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.
The category provides a default implementation using generator.
countApproximate – approximate number of objects
Cat::CombinatorialClass::countApproximate(<size s, constraints c>)
Returns the order of magnitude of the result of count(...).
The only quality requirement is that it should return infinity if and only if count returns infinity. The main purpose is for heuristic decisions depending on the order of magnitude of the size of the combinatorial class.
The category provides a default implementation using count if the later is non trivial.
list – list of the objects
Cat::CombinatorialClass::list(<size s, constraints c>)
Returns whether the combinatorial class is finite, or UNKNOWN.
The category provides a default implementation using countApproximate if the later is defined.
list – list of the objects
Cat::CombinatorialClass::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 list returns the list 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.
The category provides a default implementation using generator.
generator – generator for the objects
Cat::CombinatorialClass::generator(<size s, constraints c>)
Returns a generator for the objects of the class. If s or c is given, returns a generator for the objects of the class of the size s satisfying the extra constraints c.
This category provides the following methods that can be used as default implementations of cl::generator for cl a class in this category:
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;
So for example, to set cl::generator to cl::generatorFromList requires the implementation of cl::list.
first – first object
Cat::CombinatorialClass::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.
last – last object
Cat::CombinatorialClass::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.
Next – next object
Cat::CombinatorialClass::Next(dom 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.
previous – previous object
Cat::CombinatorialClass::previous(dom 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.
rank – rank object
Cat::CombinatorialClass::rank(dom o, <size s, constraints c>)
Returns the rank of the object o in the list of the objects belonging to the 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.
unrank – unrank object
Cat::CombinatorialClass::unrank(nonnegative integer 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.
random – random object
Cat::CombinatorialClass::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.
_less – comparison of two objects
Cat::CombinatorialClass::_less(dom o1, dom o2)
Whenever it is possible, this method compares the objects o1 and o2 and returns TRUE if o1 is smaller than o2.
This method is optional.
generatingSeries – the generating series of the class
Cat::CombinatorialClass::generatingSeries(variable z)
The generating series of a class is defined as
,
where 
is the set of objects in 
of size 
. Thus the coefficient of 
in the generating series 
is the number of objects of size 
. Whenever it is possible, this method returns an expression for the generating series.
Default Count/List Methods
The following methods are provided to help writing a combinatorial class. They are not supposed to be called directly, they are here rather to provide default implementations to other methods.
Note that these default implementations can be very inefficient in time or space compared to ad-hoc implementations.
countFromGenerator – count the number of objects using generation
Cat::CombinatorialClass::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 method if nothing else is provided.
listFromGenerator – list the number of objects using generation
Cat::CombinatorialClass::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 size-doubling arrays to avoid the reallocation of the list at each step.
This is the default implementation for the list method if nothing else is provided.
Default Generator Implementations
The following methods can be used to provide default implementations for cl::generator with cl a combinatorial class. This category tries, 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 none of the preceding methods has been successful because the necessary methods are not provided in cl, an error is raised at the first call of cl::generator. This also applies to the first call of cl::count or cl::list if they are using a default implementation via generator.
generatorFromNext – generator for the objects using first and Next
Cat::CombinatorialClass::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 usually a relatively good implementation with respect to time and space.
This is the default implementation for the generator methods if first and Next are provided.
generatorFromPrevious – generator for the objects using last and previous
Cat::CombinatorialClass::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 usually a relatively good implementation with respect to time and space.
generatorFromUnrank – generator for the objects using unrank
Cat::CombinatorialClass::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 usually a relatively good implementation with respect to time and space.
generatorFromList – generator for the objects using list
Cat::CombinatorialClass::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.
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 considering that a vector is a binary expansion of a number. This is done by searching the first 
and replacing the initial sequence 
by 
. 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]);
We can use this to build a combinatorial class. We have to define isA for the type checking and first and Next for generation :
domain ZeroOneVectors
inherits Dom::BaseDomain;
category Cat::CombinatorialClass, Cat::FacadeDomain(DOM_LIST);
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)
The method list is provided by Cat::CombinatorialClass via the default implementation using generator:
ZeroOneVectors::list(3)
together with the method generator:
g := ZeroOneVectors::generator(2):
g(), g(), g(), g(), g()
The following useful shortcut is also defined
ZeroOneVectors(3)
A default implementation is provided for the count method:
ZeroOneVectors::count(4)
However, this is very slow since it simply generates all the elements and counts them:
ZeroOneVectors::count(10);
time(ZeroOneVectors::count(10))
Whenever possible, it is better to implement the count method:
ZeroOneVectors::count := i -> 2^i:
ZeroOneVectors::count(10);
time(ZeroOneVectors::count(10))
