How do I memoize this LIS python2.7 algorithm properly?

Question

I'm practicing Dynamic Programming and I am writing the Longest Increasing Subsequence problem.

I have the DP solution:

def longest_subsequence(lst, lis=[], mem={}):
  if not lst:
    return lis
  if tuple(lst) not in mem.keys():
    if not lis or lst[0] > lis[-1]:
      mem[tuple(lst)] = max([longest_subsequence(lst[1:], lis+[lst[0]], mem), longest_subsequence(lst[1:], lis, mem)], key=len)
    else:
     mem[tuple(lst)] = longest_subsequence(lst[1:], lis, mem)
  return mem[tuple(lst)]

And a non-memoized version

def longest_subsequence(lst, lis=[]):
  if not lst:
    return lis
  if not lis or lst[0] > lis[-1]:
    result = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
  else:
    result = longest_subsequence(lst[1:], lis)
  return result

However, the two functions have different behaviours. For example, the test case longest_subsequence([10,9,2,5,3,7,101,18]) fails for the memoized version.

>>> longest_subsequence([10,9,2,5,3,7,101,18])
[10, 101]

The non-memoized version is fully correct however (although much slower).

>>> longest_subsequence([10,9,2,5,3,7,101,18])
[2, 5, 7, 101]

what I am doing wrong?

I've only given your code a cursory look, but by any chance have you called the memoized version in your interpreter session before? Mutable default arguments retain state. That may be messing you up. — juanpa.arrivillaga, Oct 12 '16 at 08:08
Nope! both of those results are from fresh sessions @juanpa.arrivillaga — ylun.ca, Oct 12 '16 at 08:09

score 4 · Accepted Answer · edited May 23 '17 at 12:00

Your state depends on both lst and previous item you have picked. But you are only considering the lst. That is why you are getting incorrect results. To fix it you just have to add previous item to your dynamic state.

def longest_subsequence(lst, prev=None, mem={}):
  if not lst:
    return []
  if (tuple(lst),prev) not in mem:
    if not prev or lst[0] > prev:
      mem[(tuple(lst),prev)] = max([[lst[0]]+longest_subsequence(lst[1:], lst[0]), longest_subsequence(lst[1:], prev)], key=len)
    else:
     mem[(tuple(lst),prev)] = longest_subsequence(lst[1:], prev)

  return mem[(tuple(lst),prev)]

print longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])

Note that using the tuple(list) as your dynamic state is not a very good idea. You can simply use the index of the item in the list that you are checking instead of the whole list:

def longest_subsequence(lst, index=0, prev=None, mem={}):
  if index>=len(lst):
    return []
  if (index,prev) not in mem:
    if not prev or lst[index] > prev:
      mem[(index,prev)] = max([[lst[index]]+longest_subsequence(lst, index+1, lst[index]), longest_subsequence(lst, index+1, prev)], key=len)
    else:
      mem[(index,prev)] = longest_subsequence(lst,index+1, prev)

  return mem[(index,prev)]

print longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])

For more efficient approaches you can check this question.

So there is actually a case that breaks this memoized version that I just discovered, please see edit! — ylun.ca, Oct 12 '16 at 20:47

score 0 · Answer 2 · answered Oct 12 '16 at 20:54

So I had just discovered that Tempux's answer did not work for all cases.

I went back and through about encapsulating the entire state into the memoization dictionary and thus added tuple(lis) as part of the key. Also, the lst index trick may not be as easy to implement since I am mutating lst through the recursion, hence why I am using tuple() as my keys.

The reasoning behind what I did is that multiple lis may have the same [-1] value. So, with this new state, the code is:

def longest_subsequence(lst, lis=[],mem={}):
  if not lst:
    return lis
  if (tuple(lst),tuple(lis)) not in mem:
    if not lis or lst[0] > lis[-1]:
      mem[(tuple(lst),tuple(lis))] = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
    else:
     mem[(tuple(lst),tuple(lis))] = longest_subsequence(lst[1:], lis)
  return mem[(tuple(lst),tuple(lis))]

This works for all cases I have tested so far.

I have updated the answer. I should warn you that using `tuple(lst)` and `tuple(lis)` as dynamic states highly increase the complexity of the program. — Saeid, Oct 13 '16 at 03:51
awesome, yea i realised this, the memory usage becomes quite high over large inputs. I'll probably try to implement this using indices later on — ylun.ca, Oct 13 '16 at 04:09

How do I memoize this LIS python2.7 algorithm properly?

2 Answers2