DrRacket - 找到最长的递增子序列

Question

我想创建用于查找 LIS 的代码。我的代码不能很好地工作。例如，如果输入是 '(1 3 5 10 9 6 7)，输出应该是 '(1 3 5 6 7) 但我的程序 return '(1 3 5 10)。我究竟做错了什么？我有没有编码二叉树然后找到更高的高度？或者我可以用最简单的方式编写这个程序吗？

(define (return_sequence N lst)
  (cond
    [(empty? lst) '()]
    [(< N (first lst)) (cons                           
                           (first lst)
                           (return_sequence (first lst) (rest lst))
                           )]
    [else (return_sequence N (rest lst))]
  )
)

(define (find_longest lst1 lst2)
  (cond
    [(empty? lst1) lst2]
    [(empty? lst2) lst1]
    [(< (length lst1) (length lst2)) lst2]
    [else lst1]
  )
)

(define (LIS lst) 
  (cond
    [(empty? lst) '()]
    [else (find_longest
           (cons
            (first lst)
            (return_sequence (first lst) (rest lst)))
           (LIS (rest lst))
          )]
  )
)

Answer 1

在我们开始之前，先问一个问题。你认为 '(1 1) 是递增序列吗？现在，我假设你没有。

首先，注意我们可以将find-longest简化如下：

(define (find-longest lst1 lst2)
  (if (<= (length lst1)
          (length lst2))
      lst1
      lst2))

这非常低效，但我们暂时不用担心。它至少看起来比你的代码干净。

我假设您正在尝试将 (return_sequence N lst) 定义为 lst 的最长递增子序列，使得所述子序列的所有元素都大于 N。我建议你看看当你尝试 (return_sequence 1 '(4 2 3)) 时究竟会发生什么。我们应该期望结果是 '(2 3)，但实际上是 '(4).

你需要仔细考虑你想要如何处理 (< N (first lst)) 的情况，并确保你没有犯一个愚蠢的错误（剧透 - 你正在犯一个愚蠢的错误）。

编辑：假设 (< N (first lst))。所有元素都大于 N 的 lst 的最长递增子序列包含或不包含 (first lst)。为了找到不存在的最长子序列，我们计算 (return_sequence N (rest lst))。为了找到最长的子序列，我们计算 (cons (first lst) (return_sequence (first lst) (rest lst))。相关的 cond 子句变为

[(< N (first lst)) (find_longest 
                      (cons (first lst) 
                            (return_sequence (first lst) (rest lst)))
                      (return_sequence N (rest lst)))]

这解决了您的问题。

另一方面，添加 minus-infinity 的值非常有帮助，条件是此值始终小于任何其他值。在那种情况下，我们可以做

(define (LIS lst)
   (return_sequence minus-infinity lst))

这样做需要一点小聪明，但这是可能的。

事实上，添加 minus_infinity 的一种巧妙方法是向 return_sequence 传递的不是数字 N，而是函数 (lambda (x) (< N x))。然后，您可以写 (less_than_N (first list)) 而不是行 (< N (first list))。然后，你可以 (define (minus_infinity x) #t).

也可以使用 gensym 创建一个新符号并将其设置为 minus_infinity。然后你想做一些相当厚颜无耻的事情，比如

(define minus_infinity (gensym))

(define (return_sequence N lst)
 (let ((< (lambda (a b) (or (equal? a minus_infinity) (< a b)))))
   cond ...)

(define (LIS lst)
  (return_sequence minus_infinity lst))

有趣的是我们没有递归定义 (<) - (lambda (a b) (or (equal? a minus_infinity) (< a b))) 中出现的 < 是原始的 <.

最后，您尝试的算法非常慢。在 O(n log n) where n = (length lst) 中可以解决此问题。您的解决方案将是一个指数时间的解决方案，但改进它是非常重要的。

DrRacket - 找到最长的递增子序列

DrRacket - find the longest increasing subsequence

recursion

scheme

racket