edfward

Racket 和 DP

晚上在朋友的 blog 上看到一个关于 DP 的题,想起自己一直说要好好学学函数式编程,便打算试试用 racket 解决。以下是Problem Statement:

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

如朋友所说,是很简单的 Longest Increasing Subsequence 问题的变种。算法简述就是:每一个元素应该记录两个值——在子序列中最后一个位置为上升趋势的最长长度 和 最后一个位置为下降趋势的最长长度。 前者记为DP[*][0]后者记为DP[*][1]的话状态转移方程应该是:

DP[i][0] = max{DP[x][1]} + 1 for x < i and sequence[i] < sequence[x]
DP[i][1] = max{DP[x][0]} + 1 for x < i and sequence[i] > sequence[x]

老实说算法应该是很简单的,但是真用函数式编程的方式去写就发现限制很多…特别是 immutable data 这一点。

#lang racket

(define (zigzag seq)
  (letrec ([find-max-pairs 
    (lambda (n sq)
      (letrec ([find-candidates
        (lambda (fun fc-seq)
          (if (null? fc-seq) (list 0)
            (let* ([s (car fc-seq)]
              [sd (cdr s)]
              [pick (if (eqv? fun >)
                cadr
                car)])
            (if (fun n (car s))
              (cons (pick sd) 
                (find-candidates fun (cdr fc-seq)))
              (find-candidates fun (cdr fc-seq))))))])
      (if (null? sq) (list 1 1)
        (list (+ 1 (apply max (find-candidates > sq)))
          (+ 1 (apply max (find-candidates < sq)))))))]
    [build-records (lambda (record real-seq)
      (if (null? real-seq) record
        (let ([hd (car real-seq)])
          (build-records 
            (cons (cons hd 
              (find-max-pairs hd record))
            record)
            (cdr real-seq)))))]
    [fin-records (build-records null seq)])    
  (apply max (foldl append null
      (map (lambda (i) (cdr i)) fin-records)))))

zigzag 接受一个 sequence,build-records 建立每个元素对应的DP[*][0]DP[*][1](具体的形式类似于[(x1 x2 x3),(y1 y2 y3)…],每个tuple的第一个元素是对应的 sequence 值,后面就是DP用到的参数了),find-max-pairs 通过已经有的DP队列的信息找到当前元素的两个值(它本身又通过 find-candidates 去根据状态转移方程里的条件拿到对应的队列)。说起来简单,写起来各种cons实在是相当绕脑(列了两大页草稿纸…)。

以及,代码可读性确实是个很大的问题…