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.