Longest Increasing Subsequence
April 18th, 2006 at 9:16 amI’ve posted a new code snippet to the programs and code page - an implementation of 3 different algorithms for solving the Longest Increasing Subsequence problem.
The implementations are:
- Using the the Longest Common Subsequence algorithm on a sequence with its sorted self:
O(n^2) - Using a dynamic programming algorithm described here . It is also
O(n^2), but faster than (1) because of better constants and less generality. - Using a greedy algorithm described here, that runs in
O(n*log(n))
April 18th, 2006 at 3:00 pm
Just a little pointer: the usual way to sort an Array randomly in Ruby is simply sorting by
rand. Example:def shuffle_sequence!( a )
a.sort! { rand }
end
sequence = (0..10).to_a
shuffle_sequence! sequence # => randomized array
April 18th, 2006 at 4:05 pm
My implementation follows the Fisher Yates shuffle algorithm. See:
http://pleac.sourceforge.net/pleac_ruby/arrays.html
Also, yours is O(n*logn) which is an overkill for an obviously linear task.