From the seqfan forum I picked up the computing of the following triangle:
({.~1+1 i:~ '1'=])"1 ": > F 10
1
0 1
1 0 1
0 2 0 1
2 0 2 0 1
0 4 0 2 0 1
3 0 5 0 2 0 1
0 7 0 5 0 2 0 1
5 0 9 0 5 0 2 0 1
0 12 0 10 0 5 0 2 0 1
The terms on a row are computed recursively (see verb xT and T).
The triangle can be computed with J as follows:
1. explicit
xT=: 4 :0 "0
select. * x-y
case. _1 do. 0
case. 0 do. 1
case. do.
if. 1=2| x-y do. 0 return. end.
if. 0=y do. +/ (xT i.@>:)<.-: x else. (x xT&<: y) + (x-+:y) xT y end.
end.
)
xF=: <@({: xT ])\@i.
or
2. tacit:
T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-) "0
F=: <@({: T ])\@i.
example:
,. F 9
┌─────────────────┐
│1 │
├─────────────────┤
│0 1 │
├─────────────────┤
│1 0 1 │
├─────────────────┤
│0 2 0 1 │
├─────────────────┤
│2 0 2 0 1 │
├─────────────────┤
│0 4 0 2 0 1 │
├─────────────────┤
│3 0 5 0 2 0 1 │
├─────────────────┤
│0 7 0 5 0 2 0 1 │
├─────────────────┤
│5 0 9 0 5 0 2 0 1│
└─────────────────┘
The interesting thing here is the major speed up by applying double
memoization:
( I use the tacit verbs)
T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-) M."0
F=: <@({: T ])\@i. M.
You can follow the stepwise speed up by first adding M. to T and after
that also to F and comparing the timings. The speed up is huge.
FYI.
BTW the triangle is of some interest: try summing the rows
--
Met vriendelijke groet,
@@i = Arie Groeneveld
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
