[Jprogramming] Greatest Increasing Subsequence

[Raul Miller]

That blew up for me, and I did not feel motivated to dump my existing
j session, so I rewrote it a bit:

NB. dyads
   e=:  (1 + {:@[ < ]) {. [ ; ,
   h=:  [: ; e&.>

NB. monads
   g=: (}.@] ;~ {.@] ; (h {.))&>/
   c=: ({::~ [: (i. >./) #@>)@>@{.
   d=: (<_) ; ]
   f=: ([: c g^:(#@(>@{:)))@d

I don't think this is much faster. But it seems to still work.

Those sub-expressions could use better names.

Thanks,

-- 
Raul

On Fri, Sep 2, 2016 at 2:06 PM, Xiao-Yong Jin <jinxiaoyong at gmail.com> wrote:
> Came up with this:
>
>    f=.u at d
>    u=.[: c g^:(#@n)
>    d=.(<_) ; ]
>    c=.[: > s {~ [: {.@\: #@>@s
>    g=.}. at n ;~ {. at n ; s h {. at n
>    n=.>@{:
>    s=.>&{.
>    h=.[: ; e&.>
>    e=.<@[`([ ; [ , ])@.t
>    t=.{:@[ < ]
>    f 7 4 4 5 2 7 1 8 13 2 10 4 9 1 4 5 5 4 3 10 3 4 5 8 15 7 11 19
> 1 2 3 4 5 7 11 19
>
> Let me know if you can optimize it.
>
>> On Sep 2, 2016, at 11:30 AM, Raul Miller <rauldmiller at gmail.com> 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,
>>
>> --
>> Raul
>>
>>
>>
>> On Fri, Sep 2, 2016 at 12:18 PM, jonghough via Programming
>> <programming at jsoftware.com> wrote:
>>>
>>>
>>> Yes, Raul is absolutely correct. And the flaw (in my solution, at least) is obvious now. I'll try for a correct solution again tomorrow.
>>>
>>>
>>>
>>>
>>> From: 'Mike Day' via Programming
>>>
>>> Sent: Saturday, September 3, 00:26
>>>
>>> Subject: Re: [Jprogramming] Greatest Increasing Subsequence
>>>
>>> To: 'Mike Day' via Programming
>>>
>>>
>>>
>>> Same problem with my version, which was faster but equally wrong! Mike On 02/09/2016 14:57, Raul Miller wrote: > Actually, if we try your approach on -8 2 4 3 1 6 we get _8 _2 _1 > instead of _8 _4 _3 _1. > > Here's a brute force O(2^n) approach that I hacked up earlier - it > obviously only works on short lists: > > increasing=: (-: /:~)@#~"1 #:@i.@^~&2@# > longestinc=: ] #~ [: (#~ ([: (= >./) +/"1)) #:@I. at increasing > > We can do better, of course, but I have some other things I want to > deal with, first. > > 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
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm