Cat::CombinatorialClass
--
the category of combinatorial classes
Cat::CombinatorialClass
represents the category of combinatorial classes that is the
categories of sets that can be enumerated, counted...
Cat::CombinatorialClass()
Cat::BaseCategory
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.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.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
.
isA
, list
, generator
take
the very same argument.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.
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"
.
The standard common interface of a domain that belongs to Cat::CombinatorialClass
.
isA(object x, <, size s, constraints c>)
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.
size(object x)
count( <size s, constraints c>)
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
.
list( <size s, constraints c>)
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
.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.
generator( <size s, constraints c>)
s
or
c
is given, returns the a generator for the objects of the class of
the size s
satisfying the extra constraints c
.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
;
first( <size s, constraints c>)
s
or
c
is given, returns the first object of the class of
the size s
satisfying the extra constraints c
.
last( <size s, constraints c>)
s
or
c
is given, returns the last object of the class of
the size s
satisfying the extra constraints c
.
Next(object o, <size s, constraints c>)
s
or
c
is given, returns the next object of the class of
the size s
satisfying the extra constraints c
.
previous(object o, <size s, constraints c>)
s
or
c
is given, returns the previous object of the class of
the size s
satisfying the extra constraints c
.
rank(object o, <size s, constraints c>)
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
.
unrank(number n, <size s, constraints c>)
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( <size s, constraints c>)
s
or c
is
given, returns a random object of the class of the size s
satisfying the extra constraints c
.
_less( <object o1, object o2>)
o1
and o2
and
returns true if o1
is smaller than o2
.
generatingSeries( <variable z>)
"generatingSeries"
return an
expression for the generating series.
Note that these default implementations can be very inefficient in time or space compared to ad-hoc implementations.
countFromGenerator( <size s, constraints c>)
This is the default implementation for the count methods if nothing is provided.
listFromGenerator( <size s, constraints c>)
This is the default implementation for the list methods if nothing is provided.
"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
"first"
and "Next"
generatorFromNext( <size s, constraints c>)
"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.
"last"
and "previous"
generatorFromPrevious( <size s, constraints c>)
"previous"
at each step, which is most of the time a relatively
good implementations with respect to time and space.
"unrank"
generatorFromUnrank( <size s, constraints c>)
"unrank"
at each step, which is most of the time a relatively
good implementations with respect to time and space.
"list"
generatorFromList( <size s, constraints c>)
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, 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
Cat::CombinatorialClass
is a new category
MuPAD Combinat, an open source algebraic combinatorics package