Cat::CombinatorialModule – the category of combinatorial modules
Cat::CombinatorialModule represents the category of combinatorial modules.
Details:
A Cat::CombinatorialModule is a combinatorial class equiped with a structure of module. Namely,
comes with generators
in
and operators
from
to
such that each element
in
is obtained from some generator by the successive application of the generators:
.
The rank of an element is the minimum of the number of operators to be applied over one generator in order to get
. The generators of the module have rank
.
The main functionalities provided by this categories are the generation of all the elements of the combinatorial module, and the drawing of the graph depicting the module structure. The drawing is currently done by exporting a graph descriptions in the dot language, suitable for previewing, manipulation, and high quality drawing by the http://www.graphviz.org/ software suite.
Entries
"moduleGenerators" |
This mandatory list contains the generators of the module. |
"operators" |
This mandatory entry implements the operators acting on the module. In the simplest form, this entry can be a simple list of functions which each take an element of |
list – list of elements of the module
Returns the list of all the elements of the module. The default implementation is to use successive application of the operators over the module generators and their successors (depth first search, with usual time complexity and
memory complexity).
listGraded – graded list of elements of the module
Returns all the elements of the module, as a table associating to each rank the elements of that rank.
dotClass – the graph of the module, in dot format
Returns the graph depicting the structure of the module, as a string in dot format.
dotClassGraded – the graded graph of the module, in dot format
Returns the graph depicting the structure of the module, as a string in dot format, with extra layout information so that nodes of same rank are drawn at the same level.
The Depth option can specify the number of rows one likes to drawn in the graded graph.
When a function is called with the Fibers option, the graph of the combinatorial class is splitted in classes, see the example 1 for details.
We define the combinatorial module permutohedron of order 3:
domain permutohedron4
inherits Dom::BaseDomain;
category Cat::CombinatorialModule,
Cat::FacadeDomain(DOM_LIST);
moduleGenerators:= [[1,2,3,4]];
operators:= [x-> combinat::words::swapDecrease(x,1),
x-> combinat::words::swapDecrease(x,2),
x-> combinat::words::swapDecrease(x,3)];
end:
Note that operators could alternatively be defined as a single function x -> [combinat::words::swapDecrease(x,i) $i=1..3].
Now, we generate the list of all the elements:
permutohedron4::list();
This one is the graded list:
permutohedron4::listGraded();
This is the dot graded expression of the domain:
print(Unquoted, permutohedron4::dotClassGraded())
digraph G {
node [shape=plaintext];
N_1 [label = " [1, 2, 3, 4] " ];
N_2 [label = " [2, 1, 3, 4] " ];
N_1 -> N_2 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_3 [label = " [1, 3, 2, 4] " ];
N_1 -> N_3 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_4 [label = " [1, 2, 4, 3] " ];
N_1 -> N_4 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
{rank=same; N_2; N_3; N_4; }
N_5 [label = " [2, 3, 1, 4] " ];
N_2 -> N_5 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_6 [label = " [2, 1, 4, 3] " ];
N_2 -> N_6 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_7 [label = " [3, 1, 2, 4] " ];
N_3 -> N_7 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_8 [label = " [1, 3, 4, 2] " ];
N_3 -> N_8 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_4 -> N_6 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_9 [label = " [1, 4, 2, 3] " ];
N_4 -> N_9 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
{rank=same; N_5; N_6; N_7; N_8; N_9; }
N_10 [label = " [3, 2, 1, 4] " ];
N_5 -> N_10 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_11 [label = " [2, 3, 4, 1] " ];
N_5 -> N_11 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_12 [label = " [2, 4, 1, 3] " ];
N_6 -> N_12 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_7 -> N_10 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_13 [label = " [3, 1, 4, 2] " ];
N_7 -> N_13 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_8 -> N_13 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_14 [label = " [1, 4, 3, 2] " ];
N_8 -> N_14 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_15 [label = " [4, 1, 2, 3] " ];
N_9 -> N_15 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_9 -> N_14 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
{rank=same; N_10; N_11; N_12; N_13; N_14; N_15; }
N_16 [label = " [3, 2, 4, 1] " ];
N_10 -> N_16 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_11 -> N_16 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_17 [label = " [2, 4, 3, 1] " ];
N_11 -> N_17 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_18 [label = " [4, 2, 1, 3] " ];
N_12 -> N_18 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_12 -> N_17 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_19 [label = " [3, 4, 1, 2] " ];
N_13 -> N_19 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_20 [label = " [4, 1, 3, 2] " ];
N_14 -> N_20 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_15 -> N_18 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_15 -> N_20 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
{rank=same; N_16; N_17; N_18; N_19; N_20; }
N_21 [label = " [3, 4, 2, 1] " ];
N_16 -> N_21 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_22 [label = " [4, 2, 3, 1] " ];
N_17 -> N_22 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_18 -> N_22 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_23 [label = " [4, 3, 1, 2] " ];
N_19 -> N_23 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_19 -> N_21 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
N_20 -> N_23 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
{rank=same; N_21; N_22; N_23; }
N_24 [label = " [4, 3, 2, 1] " ];
N_21 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 1 " ];
N_22 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 2 " ];
N_23 -> N_24 [color = "#000000", fontcolor = "#000000", label = " 3 " ];
}
Which produces this dot picture: 1
Graph of the permutohedron of size 4
The Fibers option of the dotClassGraded function provides a way to restrict the permuthohedron to classes. The next example pictures the plactic classes, that is, the permutations that give the same tableau by the Schensted insertion algorithm.
permutohedron4::dotClassGraded(Fibers= (z -> combinat::tableaux::schensted(z)[1]))
The output produces this dot picture: 1
Plactic classes on the permutohedron of size 4
In this example, we implement an (admittedly trivial) combinatorial module whose elements are with two (partial) operators
and
such that
and
. We want the names
and
to appear as labels on the edges of the module graph. To this end, we define operators as a single function which returns both images
and
, and use the gadget combinat::classes::valuesOfTable to label them with the names
and
of the operators:
domain sl4
inherits Dom::BaseDomain;
category Cat::CombinatorialModule, Cat::FacadeDomain(DOM_INT);
moduleGenerators:= [1];
operators :=
proc(m: dom)
begin
combinat::classes::valuesOfTable(
e = if m > 1 then m-1 else FAIL end_if,
f = if m < 5 then m+1 else FAIL end_if
)
end_proc;
end_domain:
sl4::list()
Changes in MuPAD 4.0
New Function.