LCS(longest common subsequence) in Scheme

Question

I try to use Scheme to implement LCS algorithm, but there is a bug.

(define X (list #\A #\B #\C #\B #\D #\A #\B))

(define Y (list #\B #\D #\C #\A #\B #\A))

(define prefix (lambda (i s) (if (= i 0) '() (cons (car s) (prefix (- i 1) (cdr s))))))

(define (pick ith s) (if (= ith 1) (car s) (pick (- ith 1) (cdr s))))

(define (LCS x y) (define (optimal i j) (cond ((or (= i 0) (= j 0)) 0) ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1)))) (else (max (LCS (prefix (- i 1) x) y) (LCS x (prefix (- j 1) y)))))) (optimal (length x) (length y)))

1 ]=> (load "lcs.scm")

;Loading "lcs.scm"... done ;Value: lcs

1 ]=> (lcs X Y)

;Value: 5

The result should be 4, I do not know where is the bug.

merlyn merlyn · Accepted Answer · 2018-07-01T16:34:27

You are getting the error because your final recursive call in optimal is incorrect. You are taking the prefix i-1 for x or j-1 for y but what about the other. j and i might be less than the length of the respective strings, and as such, you are need to prefix the argument accordingly.

The following code works correctly.

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (LCS (prefix (- i 1) x) (prefix j y)) (LCS (prefix i x) (prefix (- j 1) y))))))
  (optimal (length x) (length y)))

Note that this problem only exists because you are mixing two different kinds of calls. One that call LCS on prefixes and another that calls optimal with lesser i and j. You could replace LCS calls with optimal for a simpler solution.

(define (LCS x y)
  (define (optimal i j)
    (cond
      ((or (= i 0) (= j 0)) 0)
      ((eq? (pick i x) (pick j y)) (+ 1 (optimal (- i 1) (- j 1))))
      (else (max (optimal (- i 1) j) (optimal i (- j 1))))))
  (optimal (length x) (length y)))

LCS(longest common subsequence) in Scheme

1 Answers