Essays/Longest Increasing Subsequence
< Essays
Jump to navigation
Jump to search
Find the longest subsequence of a given list such that the elements of the subsequence are in ascending order.
The problem is a classic, described with a solution here. The solution is translated into J below.
The J version below keeps an array of the active values as well as an array of active indexes, to avoid having to fetch all the values for each search. It returns the indexes of the atoms in the subsequence.
NB. Find the longest ascending subsequence in y
NB. y is a list of numbers
NB. Result is indexes of the values that form the largest ascending sequence in y
longascseq =: 3 : 0"1
NB. Initialize the arrays
valueofminendvalue =. indexofminendvalue =. 0$0
predecessor =. (#y)$2
NB. process the input
for_v. y do.
NB. j{indexofminendvalue is the index in the original input of the smallest
NB. input value that ends a sequence of length j+1. valueofminendvalue is
NB. the corresponding value.
NB. When a new value v comes in, we see how many previous values are smaller;
NB. calling that value j, we see that the new value becomes the smallest value
NB. that ends a subsequence of length j+1
if. (#valueofminendvalue) = j =. valueofminendvalue I. v do.
NB. New highest value (and therefore new greatest length): extend the arrays
valueofminendvalue =. valueofminendvalue , v
indexofminendvalue =. indexofminendvalue , v_index
else.
NB. New low value for an existing length: update for that length
valueofminendvalue =. v j} valueofminendvalue
indexofminendvalue =. v_index j} indexofminendvalue
end.
NB. Get a snapshot of the predecessor to the added point at the time it was
NB. added. This predecessor is given by the end of the next-shorter subsequence.
predecessor =. (indexofminendvalue {~ <: j) v_index} predecessor NB. wraps if j=0, but who cares?
end.
NB. Reconstruct the chain of predecessors from the end
predecessor {~^:(i.-#indexofminendvalue) {: indexofminendvalue
)
A simple example follows.
l =: 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
longascseq l
6 9 20 21 22 25 26 27
l{~longascseq l
1 2 3 4 5 7 11 19
See also
Contributed by Henry Rich.