Essays/Longest Increasing Subsequence

From J Wiki
Jump to: navigation, 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.