combinat-0.2.5.0: Generation of various combinatorial objects.

Math.Combinat.Trees.Nary

Description

N-ary trees.

Synopsis

# regular trees

ternaryTrees :: Int -> [Tree ()]Source

Ternary trees on n nodes (synonym for regularNaryTrees 3)

Arguments

 :: Int degree = number of children of each node -> Int number of nodes -> [Tree ()]

regularNaryTrees d n returns the list of (rooted) trees on n nodes where each node has exactly d children. Note that the leaves do not count in n. Naive algorithm.

Arguments

 :: [Int] set of allowed number of children -> Int number of nodes -> [Tree ()]

All trees on n nodes where the number of children of all nodes is in element of the given set. Example:

 mapM_ printTreeVertical
$map labelNChildrenTree_$ semiRegularTrees [2,3] n

[ length $semiRegularTrees [2,3] n | n<-[0..] ] == [1,2,10,66,498,4066,34970,312066,2862562,26824386,...]  The latter sequence is A027307 in OEIS: https://oeis.org/A027307 Remark: clearly, we have  semiRegularTrees [d] n == regularNaryTrees d n  countTernaryTrees :: Integral a => a -> IntegerSource # = \frac {1} {(2n+1} \binom {3n} {n} countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> IntegerSource We have  length (regularNaryTrees d n) == countRegularNaryTrees d n == \frac {1} {(d-1)n+1} \binom {dn} {n}  # derivation trees derivTrees :: [Int] -> [Tree ()]Source Computes the set of equivalence classes of rooted trees (in the sense that the leaves of a node are unordered) with n = length ks leaves where the set of heights of the leaves matches the given set of numbers. The height is defined as the number of edges from the leaf to the root. TODO: better name? # ASCII drawings printTreeVertical_ :: Tree a -> IO ()Source Vertical ASCII drawing of a tree, without labels. Example:  mapM_ printTreeVertical_$ regularNaryTrees 2 3


printTreeVertical :: Show a => Tree a -> IO ()Source

Prints all labels.

Example:

 printTreeVertical $addUniqueLabelsTree_$ (regularNaryTrees 3 9) !! 666


printTreeVerticalLeavesOnly :: Show a => Tree a -> IO ()Source

Prints the labels for the leaves, but not for the nonempty nodes

Nodes are denoted by @, leaves by *.

drawTreeVertical :: Show a => Tree a -> StringSource

Nodes are denoted by (label), leaves by label.

Nodes are denoted by @, leaves by label.

# classifying nodes

classifyTreeNode :: Tree a -> Either a aSource

Left is leaf, Right is node

# left and right spines

leftSpine :: Tree a -> ([a], a)Source

The leftmost spine (the second element of the pair is the leaf node)

leftSpine_ :: Tree a -> [a]Source

The leftmost spine without the leaf node

rightSpine :: Tree a -> ([a], a)Source

The length (number of edges) on the left spine

 leftSpineLength tree == length (leftSpine_ tree)


# unique labels

addUniqueLabelsTree :: Tree a -> Tree (a, Int)Source

Adds unique labels to the nodes (including leaves) of a Tree.

Adds unique labels to the nodes (including leaves) of a Forest

# labelling by depth

labelDepthTree :: Tree a -> Tree (a, Int)Source

Attaches the depth to each node. The depth of the root is 0.

# labelling by number of children

labelNChildrenTree :: Tree a -> Tree (a, Int)Source

Attaches the number of children to each node.