[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

combinat::trees -- the domain of trees

Introduction

combinat::trees is the domain of Trees. It provides also functions for enumerating, generating, and manipulating trees.

Details

Creating Elements


combinat::trees(list)

Parameters

list- A nested list representing the tree to be created.

Details

Categories

Cat::DecomposableClass, Cat::CombinatorialClass

Related Domains

combinat::binaryTrees, combinat::labelledBinaryTrees, combinat::decomposableObjects

Entries

zero

The empty tree with zero nodes

one

The tree with one single node

dummyLabel

The dummy label which is used for unlabelled trees

Method size: size of a tree

Method count: number of trees

Method generator: generator for trees

Method list: list of the trees

Method unrank: unranking of a tree

Method random: random tree

Method nops: number of operands of a tree

Method op: operands of a tree

Method subsop: replace operands of a tree

Method _index: indexed access

Method set_index: indexed assignment

Method convert: conversion of an list into a tree

Method expr: conversion of a tree into an expression

Method print: pretty printing of a tree

Method revert: reverse of a tree

Method shape: shape of a tree

Method toWord: word from a tree

Method fromShapeAndWord: filling of a tree

Method toPoset: converting a tree into a partially ordered set.

Example 1

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
         / |   \
         |  // |            \                                     \
         |    / \     /       \
        / \   | |///// \\\\\ /  \
        |     |    | |          |
        |            |          |
                                |
                               /                           \
                                 /  /                       \   \
                                  // \   \                      |
                                   |  ///  \             \\   /  \
                                      |    |              |   |
                                          /          \       / \
                                            /        |  \    |
                                             /   /    \\
                                             |   |
                                                 |
                                                 |
                                               / | \
                                              /|\| |
                                                  /|\
        

Example 2

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]]]
        

Example 3

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
                                  |, /|\
        

Example 4

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
        

Example 5

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
                                    /   \
                                  / | \
                                   /|\
                                   |
        

Example 6

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]
        

Example 7

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]
        

Background

Super-Domain

combinat::trees

Axioms

Ax::normalRep Ax::canonicalRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package