LeafIndexingTree

tree.spad line 639 [edit on github]

LeafIndexingTree is a tree where the children of each node are totally ordered from left to right, smaller means left. The root node has an arbitrary label (= value). Each other node has as label the number of leaves in the subtree of its parent node y, consisting of all the childrens left to the edge x-y. These edges are labeled from left to right by 1,2,… Assume that there are exactly l leaves. This setting determines a bijection between {0,1,…,l-1} and the leaves, respectively the paths given as list of edge numbers from the root node to the leaves: rank and unrank. Output is inherited from Tree(NNI) and implemented in the package TreeOutput. See its documentation for more details.

#: % -> NonNegativeInteger

from Aggregate

=: (%, %) -> Boolean

from BasicType

~=: (%, %) -> Boolean

from BasicType

any?: (NonNegativeInteger -> Boolean, %) -> Boolean

from HomogeneousAggregate NonNegativeInteger

child?: (%, %) -> Boolean

from RecursiveAggregate NonNegativeInteger

children: % -> List %

from RecursiveAggregate NonNegativeInteger

childrenValues: % -> List NonNegativeInteger

childrenValues(t) considers the k children t(0), .., t(k-1) and returns the partial sums v(t0)+..+v(t(i-1)) for 1 <= i <= k.

coerce: % -> OutputForm

from CoercibleTo OutputForm

coerce: % -> Tree NonNegativeInteger

from CoercibleTo Tree NonNegativeInteger

copy: % -> %

from Aggregate

count: (NonNegativeInteger -> Boolean, %) -> NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

count: (NonNegativeInteger, %) -> NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

cyclic?: % -> Boolean

from RecursiveAggregate NonNegativeInteger

depth: % -> NonNegativeInteger

depth(t) returns the length of the longest path from root to a leaf. Should be moved to RecursiveAggregate.

distance: (%, %) -> Integer

from RecursiveAggregate NonNegativeInteger

elt: (%, PositiveInteger) -> %

from Eltable(PositiveInteger, %)

elt: (%, value) -> NonNegativeInteger

from RecursiveAggregate NonNegativeInteger

empty?: % -> Boolean

from Aggregate

empty: () -> %

from Aggregate

enumerate: % -> List List NonNegativeInteger

enumerate(t) constructs all paths from the root of t to its leaves. If a node has c children, then its edges to these children are labelled by 1..v. To get the corresponding combinatorial objects, one has to apply the appropriate pathTo... function.

eq?: (%, %) -> Boolean

from Aggregate

eval: (%, Equation NonNegativeInteger) -> % if NonNegativeInteger has Evalable NonNegativeInteger

from Evalable NonNegativeInteger

eval: (%, List Equation NonNegativeInteger) -> % if NonNegativeInteger has Evalable NonNegativeInteger

from Evalable NonNegativeInteger

eval: (%, List NonNegativeInteger, List NonNegativeInteger) -> % if NonNegativeInteger has Evalable NonNegativeInteger

from InnerEvalable(NonNegativeInteger, NonNegativeInteger)

eval: (%, NonNegativeInteger, NonNegativeInteger) -> % if NonNegativeInteger has Evalable NonNegativeInteger

from InnerEvalable(NonNegativeInteger, NonNegativeInteger)

every?: (NonNegativeInteger -> Boolean, %) -> Boolean

from HomogeneousAggregate NonNegativeInteger

grtr: (List List NonNegativeInteger, List List NonNegativeInteger) -> Boolean

grtr(path1, path2) is used to sort lists of unordered set partitions. First, according to the lexicographical order of the lengths of the subsets, then according to the entries in descending order.

hash: % -> SingleInteger

from Hashable

hashUpdate!: (HashState, %) -> HashState

from Hashable

isLeafIndexingTree?: Tree NonNegativeInteger -> Boolean

isLeafIndexingTree?(t) checks, if the given tree is a leaf indexing tree. This has to be checked by inspecting all nodes y, whether either the node is a leaf or if each value of a child x is the number of leaves which can be reached starting from the node via the edges left to the the edge y-x. The value of the root does not play a role, so it can be abitrary.

isPathToLeaf?: (%, List NonNegativeInteger) -> Boolean

isPathToLeaf?(t, ln) checks whether ln is a path from t to a leave of t, in particular two neighboured entries must satisfy a parent-child relationship. Note, that the m leaves are in 1-1-correspondence with such paths, as the graph is a tree. And also with the set {0,..m-1} the ranks.

latex: % -> String

from SetCategory

leaf?: % -> Boolean

from RecursiveAggregate NonNegativeInteger

leafIndexingTree: (NonNegativeInteger, List %) -> %

leafIndexingTree(v, lt) considers lt as the list of children and adds a parent node with value v to create a new tree with this root. Before it changes the values of the child trees value(lt(1)) = 0, value(lt(2)) = #leaves(lt(1)), value(lt(3))= #leaves(lt(1)) + #leaves(lt(2)) and so on.

leafIndexingTree: List % -> %

leafIndexingTree(lt) considers lt as the list of children and adds a parent node with value 0 to create a new tree with this root. Before it changes the values of the child trees value(lt(1)) = 0, value(lt(2)) = #leaves(lt(1)), value(lt(3))= #leaves(lt(1)) + #leaves(lt(2)) and so on.

leafIndexingTree: NonNegativeInteger -> %

leafIndexingTree(v) creates a leaf indexing tree with value v, and no children.

leafIndexingTree: Tree NonNegativeInteger -> %

leafIndexingTree(t) modifies t to become a leaf indexing tree by setting the values for the required counting.

leaves: % -> List NonNegativeInteger

from RecursiveAggregate NonNegativeInteger

less?: (%, NonNegativeInteger) -> Boolean

from Aggregate

logicFunctionTree: (NonNegativeInteger, NonNegativeInteger) -> %

logicFunctionTree(n,k) constructs the tree of all logic functions in n variables and exactly k minterms. Use with care as there are binomial(2^n,k) of them.

logicFunctionTree: NonNegativeInteger -> %

logicFunctionTree(n) constructs the tree with depth 2 for all logic function in n variables, represented in canonocial DNF-form as a sum of (s-1) of the 2^n minterms for 1 <= s <= 2^n+1 (children). For each (s-1) at the next level we choose the (t-1)-th (s-1)-subset of the 2^n minterms, for 1 <= t <= binomial(2^n, s). The path from the root to such a leaf is [s,t]. Note, a conversion function pathToLogicFunction is still missing as we need p-restricted integer and a domain LogicFunction not yet in the system. Use with care as there are 2^(2^n) of them.

map!: (NonNegativeInteger -> NonNegativeInteger, %) -> %

from HomogeneousAggregate NonNegativeInteger

map: (NonNegativeInteger -> NonNegativeInteger, %) -> %

from HomogeneousAggregate NonNegativeInteger

max: % -> NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

max: ((NonNegativeInteger, NonNegativeInteger) -> Boolean, %) -> NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

member?: (NonNegativeInteger, %) -> Boolean

from HomogeneousAggregate NonNegativeInteger

members: % -> List NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

min: % -> NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

more?: (%, NonNegativeInteger) -> Boolean

from Aggregate

nextEdge: (NonNegativeInteger, List NonNegativeInteger) -> NonNegativeInteger

nextEdge(r: NNI, lvs: List NNI) returns the largest i such that lvs(i) <= r. It is required, but unchecked, that the entries of lvs are strictly increasing from left to right. The labelling of the edges starts with 1.

node?: (%, %) -> Boolean

from RecursiveAggregate NonNegativeInteger

nodes: % -> List %

from RecursiveAggregate NonNegativeInteger

numberOfChildren: % -> NonNegativeInteger

numberOfChildren(t) returns the number of children of the root of tree t.

numberOfLeaves: % -> NonNegativeInteger

numberOfLeaves(t) counts the number of leaves of t.

numberOfNodes: (%, NonNegativeInteger) -> NonNegativeInteger

numberOfNode(t, d) counts the number of nodes of t with depth d including leaves with smaller depth.

P: (NonNegativeInteger, NonNegativeInteger) -> NonNegativeInteger

P(n,k) returns the number of unordered k - number partitions of n, e.g. P(7,3) = 4 = #{[5,1,1],[4,2,1],[3,3,1],[3,2,2]}

parts: % -> List NonNegativeInteger

from HomogeneousAggregate NonNegativeInteger

pathToPermutationCycles: (NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> List List NonNegativeInteger

pathToPermutationCycles(n,k,lp) constructs the permutation of {1,..,n} with k cycles, represented by the path from the root of its tree to a leave.

pathToSubset: (NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> List Integer

pathToSubset(n, k, lp) constructs a k-subset of {1,…,n} which corresponds to a leaf of subsetTree(n,k). Elements are in descending Order

pathToUnorderedNumberPartition: (NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> List NonNegativeInteger

pathToUnorderedNumberPartition(n,k,lp) constructs the unordered number partition of n with k components, represented by the path from the root of its tree to a leave.

pathToUnorderedSetPartition: (NonNegativeInteger, NonNegativeInteger, List NonNegativeInteger) -> List List NonNegativeInteger

pathToUnorderedSetPartition(n,k,lp) constructs the unordered set partition of n in k non-empty subsets, represented by the path from the root of its tree to a leave.

permutationCyclesTree: (NonNegativeInteger, NonNegativeInteger) -> %

permutationCyclesTree(n, k), abbreviated by [n, k] gives the tree for the permutations of {1,2,..,n} with exactly k cycles. Their number is stirling1(n,k). The constructing recursion is [n,k] = [n-k,k] + (n-1)[n-1,k-1], termination is [n,n] = [(1),(2),..,(n)], [2,1] = [(1,2)] first edge drop cycle (n), if possible, next (n-1) edges: drop n out of the cycle, where i is mapped to n, 1 <= i <= n-1. Bijections: [n-1,k-1] -> [n,k], c1*c2*..*c(k-1) +-> c1*c2*..*c(k-1)*(n) case 1 <= i <= n-1 : [n-1,k] -> [n,k], c1*c2*..*ck +-> _ c1*c2*..*cj'*..*cl where cj=(…i,n,l,,,) is the cycle where i is mapped to n while cj'=(…i,l,,,) is the cycle where n is cancelled.

randomPath: % -> List NonNegativeInteger

randomPath(t) constructs path from the root of t to one leaf. Each leaf has equal chance to be selected by random.

rank: (%, List NonNegativeInteger) -> NonNegativeInteger

rank(t, path) returns the rank of the leaf at the end of the path. This is the number starting with 0 from left to right in the natural ordering of the leaves given by the ordering of the children at each node.

retract: Tree NonNegativeInteger -> %

from RetractableFrom Tree NonNegativeInteger

retractIfCan: Tree NonNegativeInteger -> Union(%, failed)

from RetractableFrom Tree NonNegativeInteger

sample: %

from Aggregate

setchildren!: (%, List %) -> %

from RecursiveAggregate NonNegativeInteger

setCountingValues: List % -> List %

setCountingValues(lt) sets all values to satisfy the counting conditions of a leaf indexing tree.

setelt!: (%, value, NonNegativeInteger) -> NonNegativeInteger

from RecursiveAggregate NonNegativeInteger

setvalue!: (%, NonNegativeInteger) -> NonNegativeInteger

from RecursiveAggregate NonNegativeInteger

setValue: (%, NonNegativeInteger) -> %

setValue(t, v) sets v as the new value of tree t.

size?: (%, NonNegativeInteger) -> Boolean

from Aggregate

subsetTree: (NonNegativeInteger, NonNegativeInteger) -> %

subsetTree(n, k) constructs the tree with depth k for all k-subsets of an n-element set as {1,2,..,n}. Its elements are sorted in decreasing order. A path (p1,p2,..,pk) from root to a leave represents the subset {s1 := n-p1+1, s2 := s1-p2+1, …}.

unorderedNumberPartitionTree: (NonNegativeInteger, NonNegativeInteger) -> %

unorderedNumberPartitionTree(n,k), abbreviated by P(n,k), gives the tree forthe unordered number partitions of n in exactly k summands > 0. Therr number can be computed by P(n,k). Recursion is P(n,k) = P(n-k,k) + P(n-1,k-1), Termination is P(n,n) = {[1,1,..,1]}, P(n,1) = {[n]}. First edge -[1,1,,1], if smallest element >= 2, otherwise second edge drop: ..,1]. Bijections: P(n,k,>1) -> P(n-k,k), p +-> p-[1,1,..,1] P(n,k,1) -> P(n-1,k-1), p = [p1,p2,..,.p(k-1),1] +-> [p1,p2,..,.p(k-1)]

unorderedSetPartitionTree: (NonNegativeInteger, NonNegativeInteger) -> %

unorderedSetPartitionTree(n,k), abbreviated by {n,k}, gives the tree for the unordered set partitions of n in exactly k non-empty subsets, a k-clustering. Recursion is {n,k} = {n-1,k-1} + k{n-1,k}, termination is {n,n} = {{1},{2},..,{n}}, {n,1} = {{1,2,..,n}} First edge drop 1-element set {n}, next k edges 2 <= i <= k+1: drop n from the i-th subset where it is included, bijections: {n-1,k-1} -> {n,k}, c = {c1,c2, …, c(k-1)} +-> {c1,c2, …, c(k-1), {n}} case i: {n-1,k) -> {n,k}, c = {c1,c2, …, ck} +-> {c1,c2, …, c(i-1), ci union {n}, c(i+1),..,ck}

unrank: (%, NonNegativeInteger) -> List NonNegativeInteger

unrank(t, r) returns the path from top node of t to the leaf, numbered by r. Argument r must satisfy 0 <= r < numberOfLeaves(t).

value: % -> NonNegativeInteger

from RecursiveAggregate NonNegativeInteger

Aggregate

BasicType

CoercibleTo OutputForm

CoercibleTo Tree NonNegativeInteger

Eltable(PositiveInteger, %)

Evalable NonNegativeInteger if NonNegativeInteger has Evalable NonNegativeInteger

finiteAggregate

Hashable

HomogeneousAggregate NonNegativeInteger

InnerEvalable(NonNegativeInteger, NonNegativeInteger) if NonNegativeInteger has Evalable NonNegativeInteger

RecursiveAggregate NonNegativeInteger

RetractableFrom Tree NonNegativeInteger

SetCategory

shallowlyMutable