This version of "lis" is a bit more J-like, especially in using dyadic I.
instead of the diy binary search, at the expense of a slightly more
complicated set-up for the m and mx arrays.
lis =: 3 : 0
n =. #x =. y
if. 2>#x do. x return. end. NB. special case empty or singleton array
if. (-:/:~)x do. ~.x return. end. NB. special case sorted arrays
if. (-:\:~)x do. {.x return. end.
p =. n#0
NB. seed m with trailing _1 so that final L (as in wiki algorithm) can
be found
m =. n 0 } _1#~>:n
NB. set up sorted mx, with just the first element of x, so that I. works
mx =. ({.x) 1 } (<:<./x), n#>:>./x
for_i. i.n do.
xi =. i{x
lo =. mx I. xi
p =. (m{~<:lo) i } p NB. better than appending to short p for
larger x
m =. i lo } m
mx =. xi lo } mx
end.
|. x{~(p{~])^:(i.L) m{~ L =. <: m i. _1
)
Mike
On 02/09/2016 20:45, 'Mike Day' via Programming wrote:
Well, assuming for now that it does work, here's an attempt at a J
version of
the pseudo-code listed at
https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
lis =: 3 : 0 NB. longest increasing subsequence
m =. 0#~>:n =. #x =. y
L =. #p =. ''
mx =. m{x NB. added this vector for better look-up of x{~mid{m
for_i. i.n do.
'lo hi' =. 1, L
xi =. i{x
while. lo <: hi do.
mid =. >.@-: lo + hi
NB. if. xi > x{~ mid{m do. NB. next line a bit better
if. xi > mid{mx do.
lo =. >: mid
else.
hi =. <: mid
end.
end.
p =. p, m{~<:lo
m =. i lo } m
mx =. xi lo } mx NB. update my additional array
L =. L >. lo
NB. smoutput i; (x{.~ >:i); L{.m NB. diagnostic
end.
|. x{~(p{~])^:(i.L) L{m
)
It's reasonably fast on ?10000#5000 - but possibly wrong!It does
fail on an empty array.
Mike
On 02/09/2016 17:30, Raul Miller wrote:
It seems to me that the "efficient algorithm" documented on the
wikipedia page would have an analogous flaw. It is performing binary
searches on unsorted lists. That said, it does perform correctly for
this example.
Thanks,
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
