How to Solve it by Computer #8

Algorithm 4.7: Given a set of n distinct numbers, find the length of the longest monotone increasing subsequence.

Example: [2 9 4 7 3 11 8] -> [2 4 7 11] with length 4

Quite an interesting problem. I thought and tried different approaches. Here’s the problem I had or which I neglected. I thought the problem required all subsets. The idea of the algorithm in the book is to find the largest sequence given an end and then compare the length appending the next element.

However, I thought that it wouldn’t work in a case like this:

[2 3 55 4 5 56 57 58 59]

Start with index = 2:
[2 3]
-> largest subset: [2 3]

index = 3:
[2 3 55]
-> largest subset: [2 3 55]

index = 4:
[2 3 55 4]
-> largest subset: [2 3 55] OR
                   [2 3  4]

index = 5:
[2 3 55 4 5]
-> largest subset: [2 3 4 5]

I’m still wondering whether there’s a case in which we throw away a sequence which could work out as the longest one. Sadly, the author didn’t discuss the problem.

I see that there’s an inherent sub-structure. If we find the longest sequence in the last X numbers we can lengthen it by prepanding more stuff. Hm, thinking about it, that’s a good idea.

Let’s reverse the list:

[59 58 57 56 5 4 55 3 2]

Strangely, this does make more sense. Although, it’s probably equivalent. OK, new code.

We want a function which takes a list and returns a list with the largest subsets. More interesting however are the intermediate steps. We want it to give various things:

a) the current longest subsets
b) the next number

And it should return the longest subsets.

Let’s code. This took a while :D. So, we start with get-lengthy-subsets which returns a list of the largest subsets for each ‘level’.

(defn get-lengthy-subsets
  "Returns a set of vectors of the longest subsets"
  [collection]
  (loop [longest-subsets #{[]}
         coll collection]
    (if (seq coll)
      (recur
        (into longest-subsets (map #(get-increasing-coll % (first coll)) longest-subsets))
        (next coll))
      longest-subsets)))

Basically very straight forward. We start with a set with just one empty vector. Then check for each element in our set whether adding the next number is monotone bigger. We use the function get-increasing-coll for that. In case it is increasing, it returns the new vector with the number added. Otherwise it just returns the current variable.

(defn increasing?
  "Checks if a number is bigger than the last
   element of a collection"
  [coll number]
  (or (empty? coll) (> number (last coll))))


(defn get-increasing-coll
  "Returns a new collection if the number is bigger
   than the last element"
  [coll number]
  (if (increasing? coll number)
    (conj coll number)
    coll))

This function uses increasing? which checks for the increment – which also works if we start with an empty vector.

The last function which helps us to get longest subset is easy:

(defn get-longest-subset
  "Returns the longest monotone increasing subset"
  [collection]
  (last (sort-by
          count
          (get-lengthy-subsets collection))))

We just sort by the length and select the last one. Done. Finally :D