[Jprogramming] Greatest Increasing Subsequence

['Mike Day' via Programming]

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    =. >. at -: 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