While we're on this thread, I might as well share the couple pieces I have
laying around:
NB. Output a random depth vector of length y
rv=: <:@(1&= # +/\)@(|.~ >:@(i: <./)@(+/\))@(A.~ ?@!@x:@#)@($&1 , $&_1@<:)
NB. Pretty print a tree representation, given a depth vector (inspired by xash)
TM=: 3 4 $ 0 1 0 1 3 1 3 1 2 2 2 2
pp=: |:@(,/)@({&' |o+-'@(,:~ 4 * 2&=)@({::&TM@,/\.)@(0 ,~ (=>:) + 2*=)"_ 0 ~.)
The above are verbosely documented in the attached script.
NB.NB. Trees
NB.
NB. Collections of tools for working with generic tree data structures.
NB. Formally, by "tree" we mean a "plane tree", i.e. children of a node are
NB. ordered.
cocurrent 'tree'
NB.NB. Check whether list is a Ballot Sequences
NB.
NB. A "ballot sequence" S is a list of 1's and _1's that has non-negative
NB. partial sums. A ballot sequence is called "strict" if the partial sums are
NB. all strictly positive.
NB.
NB. Here are some examples:
NB.
NB. 1] 1 _1 1
NB. 2] 1 1 _1 _1 1 1 1 _1 1 _1 _1 _1
NB. 3] 1 1 1 1 1 1
NB.
NB. Here are some non-examples:
NB.
NB. 1] _1 1 1
NB. 2] _1 1 1 _1 _1 1 1 1 _1 1 _1 _1
NB. 3] _1 _1 _1 _1 _1
NB.
NB. Notice that 1 and 2 are cyclic rotation of the corresponding ballot
NB. sequences above.
bs=: (+/\ *./@:>: 0:) *. (# = _1&= +/@:+. 1&=)
NB.NB. Check whether list is a Dyck Path
NB.
NB. A "Dyck path" of length 2n is a path on the integer lattice starting at
NB. the origin (0,0) and ending at (2n,0) such that the path never dips below
NB. the x-axis.
NB.
NB. Dyck paths can be thought of as a sort of visualization of ballot
NB. sequences that sum to 0. Here is an example that corresponds to the ballot
NB. sequence (1 1 _1 _1 1 1 1 _1 1 _1 _1 _1):
NB.
NB. 3|
NB. 2| /\/\
NB. 1| /\ / \
NB. 0| / \/ \
NB. ---------------
NB. 0 . . 6 . . 12.
NB.
NB. Since the list of x coordinates is simply (i.2n), we can elide the
NB. redudancy and simply represent a Dyck path by the list of its y
NB. coordinates.
dp=: bs@(+/\^:_1)@}. *. (0 *./@:= {. , {:)
NB.NB. Generate random depth vector of length y over its uniform distribution
NB.
NB. One obtains the depth vector of a tree by starting at the root, which has
NB. depth 0, and walking around the perimeter counter-clockwise, writing down a
NB. node's depth every time it is first encountered. Here, "node depth" means
NB. its path-distance from the root. For example, the depth vector of the
NB. following tree is (0 1 2 2 3 1 2):
NB.
NB. 0 o .
NB. v < < v | ^ < <
NB. 1 o ----+---- ^
NB. < < | > > > > v \ ^
NB. v +--+--+ ^ 1 o ^
NB. v | > v | ^ v | ^
NB. 2 o ^ 2 o ^ 2 o ^
NB. > > v | ^ > >
NB. 3 o ^
NB. > >
NB.
NB. More formally, let N denote the list of nodes in depth-first pre-order
NB. traversal order and (d n) denote the depth of node n in N. Then the depth
NB. vector is (d N).
NB.
NB. The above procedure associates a unique depth vector to each tree, but it
NB. is also not hard to see that the reverse is true; no two trees have equal
NB. depth vectors.
NB.
NB. To generate a random depth vector, we exploit the fact that the set of
NB. plane trees with n nodes naturally bijects with each of the following:
NB.
NB. 1. Dyck paths of length 2n.
NB. 2. Strict ballot sequences of length 2n+1 that sum to 1, and
NB.
NB. Indeed, to see 1 all you have to do is walk counter-clockwise around your
NB. tree again and record node depths *every* time you pass a node, not skiping
NB. if it is a duplicate. Every node will be visited exactly twice, once on the
NB. way down and next on the way up; you start and end at 0; and no node has
NB. non-positive depth.
NB.
NB. For the bijection with 2, you just need to take the inverse partial sum
NB. (+/\^:_1) of the Dyck path and then prepend a 1. The reason strict ballot
NB. sequences are helpful here is because their cyclic permutations are all
NB. unique (since there are n _1's and (1 = n *. 1+2*n) always holds).
NB.
NB. Better yet, it is a short lemma that any list of n 1's and n+1 _1's has
NB. exactly one cyclic permutation that is a strict ballot sequence. This is
NB. the key fact that we leverage here.
NB.
NB. So to generate a random depth vector, the following procedure should
NB. suffice:
NB.
NB. 1. Given y, generate a random shuffle of y 1s and y-1 _1's;
NB. 2. Shift that list into a strict ballot sequence;
NB. 3. Turn the ballot sequence into a Dyck path; and finally
NB. 4. Remove the descending steps (which correspond to node revisits).
rv=: <:@(1&= # +/\)@(|.~ >:@(i: <./)@(+/\))@(A.~ ?@!@x:@#)@($&1 , $&_1@<:)
rv_z_=: rv_tree_
NB.NB. Pretty print Depth Vectors as Trees
NB.
NB. Render depth vectors visually as their corresponding trees. For example,
NB. the depth vector (0 1 2 2 3 1 2) corresponds the tree
NB.
NB. o -o
NB. / \ |-o
NB. o o | |-o
NB. / \ | , which we transpose and display like | +-o .
NB. o o o | +-o
NB. | +-o
NB. o +-o
NB.
NB. Conceptually, we construct this representation, level by level, in four
NB. stages:
NB.
NB. 1. Node classification,
NB. 2. Branch blacement, i.e. the vertical components in our representation,
NB. 3. Stem placement, the '-' in our representation, and finally
NB. 4. Formatting.
NB.
NB. Step 1 is easy. For each level L, we simply classify each node N into one
NB. of three possible categories:
NB.
NB. 1. N is neither at level L nor L+1,
NB. 2. N is at level L, and
NB. 2. N is at level L+1.
NB.
NB. Step two is a bit more subtle. The key insight is to "grow" the branches
NB. from their tips to their stalks by examining the node category above in
NB. conjunction with the current "growth state". This latter has four
NB. possibilities:
NB.
NB. 1. Not growing any branch.
NB. 2. Branch tip, i.e. start reverse-growing a new branch,
NB. 3. Branch interior, i.e. currently within a branch,
NB. 4. Branch nadir, i.e. finished growing a branch, and
NB.
NB. This gives us a total of 12 combinations---three node categories times four
NB. growth states. We start in state 1, move along the categorized nodes in
NB. reverse order, and determine our next state at each step depending on the
NB. combination of current state and current node category.
NB.
NB. We use a transition matrix to encode the transition logic, but the basic
NB. ideas is that nodes at level L+1 start growing a branch from the tip and we
NB. keep growing until reaching a node at level L.
NB.
NB. The last two steps, "stem placement" and "formatting" are quite
NB. straightforward. Stems just extand out from the nodes, and formatting
NB. simply typesets the internal integer representation into something visually
NB. pleasing.
TM=: 3 4 $ 0 1 0 1 3 1 3 1 2 2 2 2
pp=: |:@(,/)@({&' |o+-'@(,:~ 4 * 2&=)@({::&TM@,/\.)@(0 ,~ (=>:) + 2*=)"_ 0 ~.)
pp_z_=: pp_tree_
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
