Longest decreasing sequence in Lisp

问题:

I'm working on some problems for my upcoming exam and I need some help with this Lisp function. I'm working in CLISP. I have to find the longest decreasing sequence comprised only of odd numbers in a list. Example:

(longest '(13 9 3 7 4 7 5 3 2 8 15 11 9 7 3))

Should return:

(15 11 9 7 3)

The only mandatory requirement is that that the function has to be implemented recursively :)

回答1:

With contiguous subsequences, it's easy. Except I don't lisp, so I have to explain it in words.

1. Call a recursive helper, with additional arguments a) longest found so far b) length of that c) current subsequence d) length thereof. Initially these are () 0 () 0.
2. While head of list is even, recur on tail.
3. Start current with the first odd encountered, recur on tail.
4. If head is even, or head is not smaller than the previous element, the current sequence stops. Compare its length to the previously found longest sequence. If current is longer, it becomes the new longest, else forget current. Go to 2.

When the end of the list is reached, the longer of the two remembered lists is the answer.

回答2:

You could do this in one stage using recursion (which would be faster & more efficient than the method I'm about to suggest), but it may be more readable, modular, and simpler to code if you generate all of the possible solutions first, filter by the ones that are valid, and then return the best of those solutions.

To do it this way, you'll need a generator & mapping function (I'd suggest two nested maplist's for this problem), a filter function (write this one; decreasing odd; then look at lisp's 'remove-if-not funciton), and a reducing function (return the best solution (longest list) from the filtered ones).

There's a section in SICP that discusses this style of approach: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2

A signal-processing engineer would find it natural to conceptualize these processes in terms of signals flowing through a cascade of stages...

回答3:

The algorithm as in Daniel's answer translated into Haskell, with some tweaks:

longest_sub xs = g2 xs [] 0 
  where
    g2 [] a _ = a
    g2 (x:t) a i  
         | even x    = g2 t a i 
         | otherwise = g4 t [x] 1
      where
        g4 [] b j = if j>i then reverse b else reverse a
        g4 xs@(x:t) b j            
             | even x || x >= head b
                         = if j>i then g2 xs b j 
                                  else g2 xs a i 
             | otherwise = g4 t (x:b) (j+1)

In Common Lisp:

(defun longest (xs)
  (prog  ((a nil) (i 0) b j x)                  ; var decls
      G2  (if (null xs) (return (reverse a)))   ; code
          (setf x (car xs) xs (cdr xs))
          (if (evenp x)
              (go G2))
      G3  (setf b (list x) j 1)
      G4  (if (null xs)
              (if (> j i)
                  (return (reverse b))
                  (return (reverse a))))
          (setf x (car xs) xs (cdr xs))
          (when (evenp x)
              (if (> j i) (setf a b i j))
              (go G2))
          (when (>= x (car b))
              (if (> j i) (setf a b i j))
              (go G3))
          (setf b (cons x b) j (+ j 1))
          (go G4)))

Function call is a glorified GOTO after all, isn't it?

see also: prog doc page.