Q: Longest increasing subsequence — Find the longest monotonicly increasing subsequence in a sequence.
function lis(seq, result=[], prior_subseq=[], prior_subseq_idx=[]):
prior_max, prior_max_idx = prior_subseq[-1], prior_subseq_idx[-1]
next_subseq = seq[prior_max_idx]
remaining_idx = argwhere({v > prior_max for v in seq})
for idx in remaining_idx:
potential_results = lis(seq, result, prior_subseq + [seq[idx]], prior_subseq_idx + [idx])
if len(potential_result) > len(result):
result = potential_result
return result
import unittest
class TestLIS(unittest.TestCase):
def testBaseCaseZeroLength(self):
self.assertEqual(lis([]), [])
def testBaseCaseOneLength(self):
self.assertEqual(lis([1]), [1])
def testSimpleAscending(self):
self.assertEqual(lis([1, 2]), [1, 2])
def testLongerAscending(self):
self.assertEqual(lis([1, 2, 3, 4, 5, 6]), [1, 2, 3, 4, 5, 6])
def testNonMonotonic(self):
self.assertEqual(len(lis([1, 5, 2, 6, 3, 7])), 4)
if __name__ == '__main__':
unittest.main(argv=[''], exit=False)
..... ---------------------------------------------------------------------- Ran 5 tests in 0.002s OK
def lis(seq, result=[], prior_subseq=[], prior_subseq_idx=[]):
if len(seq) == 0: return []
if len(seq) == 1: return seq
if prior_subseq and prior_subseq_idx:
prior_max, prior_max_idx = prior_subseq[-1], prior_subseq_idx[-1]
else:
prior_subseq, prior_subseq_idx = [seq[0]], [0]
prior_max, prior_max_idx = seq[0], 0
remaining_subseq_idx_start = prior_max_idx + 1
remaining_subseq = seq[remaining_subseq_idx_start:]
remaining_seq_idx = [i + remaining_subseq_idx_start for (i, v) in enumerate(remaining_subseq) if v > prior_max]
for idx in remaining_seq_idx:
potential_result = lis(seq, prior_subseq + [seq[idx]], prior_subseq + [seq[idx]], prior_subseq_idx + [idx])
if len(potential_result) > len(result):
result = potential_result
return result
Done on a piece of paper. The major properties are that you can collect cases by iterating leftwards, and that you can cut down on the number of comparisons you have to make to collect new subsequences using some kind of ordered-access memory structure (simple: a list whose indices correspond with first values in the subsequence).
function lis(s):
store = [[] for n in range(max(s))]
for v in s[::-1]:
for v_slot in store[v:]:
for l in v_slot:
l.prepend(v)
if not store[v]:
store[v] = [v]
return longest_element(store)
import numpy as np
def lis(s):
if len(s) == 0: return []
store = [[] for _ in range(max(s) + 1)]
for v in s[::-1]:
for v_slot in store[v + 1:]:
for l in v_slot:
store[v].append([v] + l)
if not store[v]:
store[v] = [[v]]
macro_order = sorted(store, key=lambda l: max([len(li) for li in l]) if l else 0)
return sorted(macro_order[-1], key=lambda l: len(l))[-1]
The brute force solution is $O(n!)$, with a worst case of a completely sorted list. The optimized solution is $O(n^3)$.