Raul's expression requires that 0 be the root. If not, you need to relabel the tree so that 0 becomes the root, find the path sums, and then permute the sums at the end.
----- Original Message ----- From: Istvan Kadar <[EMAIL PROTECTED]> Date: Tuesday, May 27, 2008 9:32 Subject: Re: [Jprogramming] Displaying trees - J Wiki/Essays/Tree Sum To: Programming forum <[email protected]> > Dear Raul, > > The (+/@:{&[EMAIL PROTECTED]"1|:{&p^:a:i.#p) verb is excellent for me, > thank for it once more. > But I d'ont to apply always certainly. > Here is a new example. > > The Tree Daisplay is neat: > > t24=:23 2$2 15 2 17 2 18 15 7 15 19 17 9 18 1 18 23 19 5 > 19 6 9 14 1 16 5 4 > 6 10 14 0 14 8 16 3 10 11 8 13 8 20 11 12 20 22 12 21 > tree t24 > ┌────────────────────────────────────────────────────┐ > │ ┌─ 7 │ > │ ┌─ 15 ─┤ > ┌─ 5 ──── > 4 │ > │ │ └─ 19 > ─┴─ 6 ──── 10 ─── 11 ─── 12 ─── 21│ > │ > │ ┌─ 0 │ > │─ 2 ─┼─ 17 ─── 9 ──── 14 ─┤ ┌─ > 13 │ > │ > │ └─ 8 ──┴─ 20 ─── 22 │ > │ │ ┌─ 1 > ──── 16 ─── > 3 │ > │ └─ 18 ─┴─ > 23 │ > └────────────────────────────────────────────────────┘ > > but the Tree Sum is bad. > > The index-pair list and the v-list > > 2 ? 64772741 23759514 coordinate pair of > root node number 2. > 15 2 _3013694 _2510388 coordinate differences of > 19 15 _2131328 _7681303 23 neighbor node pairs. > 5 19 _1683264 _5442602 > 4 5 609205 _2103092 > 6 19 _6486960 3657607 > 10 6 _3196746 _5653806 > 11 10 _5146797 5941756 > 12 11 845122 5486479 > 21 12 1003461 2862276 > 7 15 _6558734 5244022 > 17 2 1981184 3419158 > 9 17 2250725 2317395 > 14 9 6801640 974269 > 0 14 85849 4351091 > 8 14 7650971 _2464341 > 20 8 691624 6018680 > 22 20 6910887 _2485036 > 13 8 1048722 _7534883 > 18 2 4420327 _2105270 > 1 18 _18622 _4733859 > 16 1 438171 _6135448 > 3 16 7889025 178765 > 23 18 7055479 971857 > > NB. The wanted sum of tree > > ]XY24=:24 2$75892139 34821427 69174446 16920385 64772741 > 23759514 77501642 > 10963702 58553660 6022129 57944455 8125221 53140759 > 17225430 55200313 > 26493148 83457261 28005995 69004650 29496067 49944013 11571624 > 4479721617513380 45642338 22999859 84505983 20471112 75806290 > 30470336 61759047 > 21249126 69612617 10784937 66753925 27178672 69193068 21654244 > 5962771913567823 84148885 34024675 46645799 25862135 91059772 > 31539639 76248547 > 22626101 > 75892139 34821427 NB. 0 > 69174446 16920385 NB. 1 > 64772741 23759514 NB. 2 NB. > list of coordinates > 77501642 10963702 NB. 3 > 58553660 6022129 NB. 4 > 57944455 8125221 NB. 5 > 53140759 17225430 NB. 6 > 55200313 26493148 NB. 7 > 83457261 28005995 NB. 8 > 69004650 29496067 NB. 9 > 49944013 11571624 NB. 10 > 44797216 17513380 NB. 11 > 45642338 22999859 NB. 12 > 84505983 20471112 NB. 13 > 75806290 30470336 NB. 14 > 61759047 21249126 NB. 15 > 69612617 10784937 NB. 16 > 66753925 27178672 NB. 17 > 69193068 21654244 NB. 18 > 59627719 13567823 NB. 19 > 84148885 34024675 NB. 20 > 46645799 25862135 NB. 21 > 91059772 31539639 NB. 22 > 76248547 22626101 NB. 23 > > Where is the error? > How may be the list p into single colon to convert? > > Regard > Istvan > > > > 2008/5/27 Roger Hui <[EMAIL PROTECTED]>: > > > > I should have pasted: > > > +/@:{&[EMAIL PROTECTED]"1|:{&p^:a:i.#p > > > > This solution should be fine if the tree is shallow, > > i.e. has average fan-out enough larger than 1. > > For example: > > > > p=: _1 p: i. 1e5 > > v=: 1e5 [EMAIL PROTECTED] 100 > > 6!:2 '+/@:{&[EMAIL PROTECTED]"1 |: {&p^:a: i.#p' > > 0.371849 > > > > However, for trees with fan-out close to 1, e.g. > > > > p=: 0 >. <: i. 1e5 > > > > The array {&p^:a: i.#p would have O(*:#p) size. > > It would not help much if you use boxed arrays, > > because the basic problem is that the algorithm > > computes the paths from the root to each node. > > > > It should be possible to have algorithm that proceeds > > as follows: for each i, for each node j, record the path > > sums from the root to node j, of a path of length > > exactly 2^i. i would be 0 1 2 ... 2^.#p . At the > end do > > a -/ over these path sums. But perhaps this measure > > is not necessary for Istvan Kadar's requirements. > > > > > > > > ----- Original Message ----- > > From: Raul Miller <[EMAIL PROTECTED]> > > Date: Sunday, May 25, 2008 16:50 > > Subject: Re: [Jprogramming] Displaying trees - J > Wiki/Essays/Tree Sum > > To: Programming forum <[email protected]> > > > > > I wrote: > > > > (Here, I have assumed that node 0 is the root node > > > > for all other nodes -- this lets me get away with not > > > > using boxes.) > > > > > > But I supplied the wrong sentence for that statement > > > > > > I should have pasted: > > > +/@:{&[EMAIL PROTECTED]"1|:{&p^:a:i.#p ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
