We have a relationship pair matrix to represent a tree.
r=:0 2, 0 1, 2 3, 2 5, 2 7, 5 6,: 1 4
which means, 2's parent is 0; 1's parent is 0; 3's parent is 2 and so on.
We have to calculate the length of the (shortest) path between two nodes.
travel=: 4 6,:0 6
which means, we need the length between the path from 4 to 6, and the
path from 0 to 6. The travel pairs can be longer, adding more
rows(like 4 6,0 6,:2 3).
Following is my first attempt.
path=:1 : '([: |: m&({~^:a:))'
length=: 4 : 0
m=. =/"1/ x path y
l1=.1 i.~"1 +./"2 m
l2=.1 i.~"1 +./"1 m
l1+l2
)
mod=: 4 : ' ({."1 y) ({:"1 y)} x'
((8$0) mod r) length 4 6,:0 6 NB. result is 5 3
I first made "length" for only one pair of nodes(rank 1) quite
quickly, and then for a longer time went through the process of
upgrading it into table version, which can take a multiple of pairs. I
don't like the process much.
How would you do this in J?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
