The best me and my father could come up with is:
s=: [: e (<<_) p&.>/@,~ <"0
p=: ] , [ ,&.> ] #~ (< {.&>) (= >./)@:* #&>@]
e=: }:@>@(#~ (= >./)@:(#&>))@>
si=: [: e (<<_) pi&.>/@,~ <"0
pi=: ] , [ ,&.> ] {~ (< {.&>) (i. >./)@:* #&>@]
Let v be a valid increasing subsequence. If n < {.v then n,v is also a valid
subsequence,
except of course if 0 = #v. This is solved by beginning the operation with a
single
subsequence containing only infinity. This also acts as a catch for numbers
which fit
in front of no longer subsequences.
s uses a basic breadth-first search, while it saves intermediate parent nodes
as well.
This is because, even if n,v is a valid subsequence, if m is much greater than
n but still
smaller than {.v, then chances are that m,v will lead to longer final
subsequences than
n,v.
Because it uses a breadth-first search, s finds all subsequences of maximal
(and equal)
length. This leads to a slow-down, and can be fixed by appending n to only the
first
subsequence found which satisfies all the conditions. However, this new
function si will
only find some of the possible subsequences. That is, if pi has to choose
between
prepending n to v1 or v2, it will only prepend it to v1. Duplicate subsequences
are still
possible if a number appears twice in the original sequence.
Another independent optimisation could be to keep track of how many elements
are left
in the total sequence, and eliminate subsequences which are shorter than the
length of
the longest subsequence minus the number of elements left, as they cannot
possibly
catch up with the longest subsequence even if it stays the same length and they
get
appended to all elements left.
I did try this however, and the resources necessary to do the filtering ended
up being
more costly than simply keeping all subsequences. Nevertheless, here are the
functions:
NB. with compression
sp=: [: e (<<_) ({:@[ f {.@[ P ])&.>/@,~ (,&.> i.@#)
P=: ] , [ ,&.> ] #~ (< {.&>) (,@[ #^:_1 (= >./)@#) #&>@]
f=: ((] >: (-~ >./)) #&>) # ]
NB. with indexing
spi=: [: e (<<_) ({:@[ f {.@[ Pi ])&.>/@,~ (,&.> i.@#)
Pi=: ] , [ ,&.> ] {~ (< {.&>) ([: {.^:(*@#)@I. ,@[ #^:_1 (= >./)@#) #&>@]
si is the fastest, and I can run it fast enough with arguments of up to 2000
elements,
but beyond that the version from Wikipedia is much faster and more economical
in space.
Cheers,
Louis
> On 02 Sep 2016, at 22:21, Raul Miller <[email protected]> wrote:
>
> NB. dyads
> e=: (1 + {:@[ < ]) {. [ ; ,
> h=: [: ; e&.>
>
> NB. monads
> g=: (}.@] ;~ {.@] ; (h {.))&>/
> c=: ({::~ [: (i. >./) #@>)@>@{.
> d=: (<_) ; ]
> f=: ([: c g^:(#@(>@{:)))@d
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
