combinat::trees
--
the domain of trees
combinat::trees
is the domain of Trees. It provides also functions for
enumerating, generating, and manipulating trees.
combinat::binaryTrees
can inherit from the data structure
and methods of combinat::trees
. combinat::labelledBinaryTrees
can inherit from
the data structure and methods of combinat::trees
. The 0-th operand of a
tree is the label of its root node.
t
is encoded as a
list whose first operand is the label of the root node of t
,
while the other operands encodes respectively the subtrees of
t
.
combinat::trees(list)
list | - | A nested list representing the tree to be created. |
combinat::trees
(list)
creates a new tree whose recursive structure is
encoded by list
(see the details above). The empty tree is encoded
as an empty list, while a non-empty tree t
is encoded as a list
whose first operand is the label of the root node of t
, while the
other operands encodes respectively the subtrees of t
.Cat::DecomposableClass
, Cat::CombinatorialClass
combinat::binaryTrees
, combinat::labelledBinaryTrees
, combinat::decomposableObjects
The empty tree with zero nodes
The tree with one single node
The dummy label which is used for unlabelled trees
size(tree t)
t
, that is its number of nodes.
count(nonnegative integer n)
n
.
generator(nonnegative integer n)
n
.
list(nonnegative integer n)
n
.
unrank(nonnegative integer n, nonnegative integer i)
n
.
random(nonnegative integer n)
n
.
nops(tree t)
t
, that is its number
of subtrees.
op(tree t)
op(tree t, nonnegative integer i)
op(tree t, nonnegative range i..j)
op(tree t, [i1, i2, ...])
subsop(tree t, i=new)
t
in which the i
-th operand is
replaced by the value new
. It can be used either to change a
subtree if i
>0 or to change the label of the root if i
=0.subsop(tree t, i1=new1, i2=new2, ...)
t
with several operands replaced at once.
_index(tree t, nonnegative integer i)
t
or FAIL if no
corresponding operand exists.
set_index(tree t, nonnegative integer i, new)
i
-th operand of t
to new
.
Returns new
in the first form, and the modified t
in
the second form.
convert(list l)
l
. Convert is called by the constructor an behaves identically.
expr(tree t)
t
, and can
be fed back into the constructor. Thus convert(expr(t))
is always
equal to t
, when t
is a tree.
print(tree t)
output::asciiArt
representation of t
suitable for basic 2D pretty printing. The labels are not printed.
revert(tree t)
t
obtained by reverting the
order of the subtrees of t
, and reverting those recursively.
shape(labelled tree t)
toWord(tree t, order p)
fromShapeAndWord(tree t, word w, order p)
t
with the element of the word
w
. This returns the tree of the same shape as t, which reading over order p
gives w back. The length of the word w
must be equal to the number of
nodes of t
.
toPoset(tree t)
t
, that is return an element of
Graph
, whose vertices are the nodes of the
tree and whose edges are the branches of the tree. This can only
be done if the labels of the nodes of the tree are distinct.One computes the list all the trees on 0 to 5 nodes writing:
>> for i from 0 to 5 do
print(combinat::trees::list(i))
end_for
[] [o] o [|] -- o o -- | / \, | | -- | -- -- o -- | o o o o | | | /|\, / \, / \, | , | | -- | | / \ | -- -- o o | o o o o / \ o o o / \ o | // \\, /|\, /|\, / \ , |, /|\, / \, / \, | , | , | | | / \ | | | | / \ | /|\ -- o o o o -- | | | | | / \, / \, | , | | | | / \ | | | --
If one wants to run through the trees of a given size, one can generate the trees one by one to save memory:
>> g:=combinat::trees::generator(4):
g(); g(); g(); g(); g(); g();
o /|\ o / \ | o / \ | o | / \ o | | | FAIL
If one wants direct access to the i-th tree of size n, it is possible in the following way:
>> combinat::trees::unrank(2,4);
o / \ |
To make statistics on general trees or to test some conjectures on the shapes of trees with a large number of nodes, one can use:
>> combinat::trees::random(91)
o / | \ | // | \ \ | / \ / \ / \ | |///// \\\\\ / \ | | | | | | | | | / \ / / \ \ // \ \ | | /// \ \\ / \ | | | | / \ / \ / | \ | / / \\ | | | | / | \ /|\| | /|\
The structure of a tree is encoded as a list of lists. To construct a tree from a list, one can use both:
>> combinat::trees([1,[1],[1,[1],[1]]]);
combinat::trees::new([1,[1],[1,[1],[1]]]);
combinat::trees::convert([1,[1],[1,[1],[1]]])
o / \ / \ o / \ / \ o / \ / \
To recover the list-format of a tree from its drawing, one uses:
>> combinat::trees::expr(%)
[1, [1], [1, [1], [1]]]
Let us compute some simple statistics on a given tree:
>> treetmp:=combinat::trees([1, [1, [1]], [1, [1], [1], [1]]])
o / \ | /|\
The size, number of operands and operands are respectively:
>> combinat::trees::size(treetmp);
combinat::trees::nops(treetmp);
combinat::trees::op(treetmp)
7 2 o o |, /|\
Change the shape of a tree:
>> treetmp := combinat::trees([1, [1, [1]], [1, [1], [1], [1]]]);
treetmp2 := combinat::trees::subsop(treetmp,
1=combinat::trees([1,[1],[1]]));
treetmp2[1]
o / \ | /|\ o / \ / \ /|\ o / \
Change the shape of the tree using another way:
>> treetmp3:=treetmp; treetmp3[1]:=combinat::trees([1,[1],[1]]);
bool(treetmp2=treetmp3)
o / \ | /|\ o / \ TRUE
To recursively revert the subtrees of a tree (making the mirror image of this tree), one uses:
>> tree:=combinat::trees([1, [1], [1, [1], [1, [1], [1], [1, [1]]], [1]]]);
combinat::trees::revert(tree)
o / \ / | \ /|\ | o / \ / | \ /|\ |
To compute a special reading of a tree, one can use:
>> valtree:=combinat::trees([6,[3,[1,[],[2]],[5,[4],[]]],[8,[7],[10,[9]]]]);
combinat::trees::toWord(valtree,Infix);
combinat::trees::toWord(valtree,RightPostfix);
o / \ / \ / \ \ / | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [9, 10, 7, 8, 4, 5, 2, 1, 3, 6]
To associate with each node of a given tree a value, thanks to a following order, one uses:
>> valtree := combinat::trees([1,[1,[1,[],[1]],[1,[1],[]]],
[1,[1],[1,[1]]]]);
valb := combinat::trees::fromShapeAndWord(valtree,
[8,4,1,7,9,5,3,10,2,6],Postfix);
combinat::trees::toWord(valb,Postfix);
o / \ / \ / \ \ / | o / \ / \ / \ \ / | [8, 4, 1, 7, 9, 5, 3, 10, 2, 6]
combinat::trees
is not a facade domains.combinat::binaryTrees
can inherit from the data structure
and methods of combinat::trees
. combinat::labelledTrees
(in construction) can inherit from
the data structure and methods of combinat::trees
. The 0-th operand of a
tree is the label of its root node. Ax::normalRep
Ax::canonicalRep
MuPAD Combinat, an open source algebraic combinatorics package