递归子列表？功能

Question

我似乎想不出如何编写一个正确的 uscheme（MIT Scheme 的衍生物）函数，该函数将 return 判断一个列表是否包含一个较小的列表。

这是我写的。

(define sublist? (xs ys)
    (if (= xs '())
        #t
        (if (= ys '())
            #f
            (if (= (car xs) (car ys))
                (sublist? (cdr xs) (cdr ys))
                (sublist? xs (cdr ys))
            )
        )
    )
)

它通过了我的大部分测试用例，除了这个测试用例。

(sublist? '(a b c) '(1 2 a 3 b 4 c 5 6))
;; this returns true while it's supposed to return false

测试用例要求子列表是连续的，中间没有随机元素。

我对如何纠正这个问题有点困惑。还有其他人有想法吗？

Answer 1

问题是你的算法太急切了——一旦找到两个相等的元素，它会立即丢弃那个元素并继续检查。实际上，找到两个相等的元素是不够的，因为如果找到不完全匹配，您的算法可能不得不回溯。

表示此类算法的最简单方法是使用辅助函数来确定子列表是否与列表中的给定位置匹配。 sublist? 函数将遍历较大列表中的每个位置以查找匹配项。

这是我的实现：

(define (sublist? xs ys)
  (define (sublist-equal? xs ys)
    (cond
      ((null? xs) #t)
      ((null? ys) #f)
      ((equal? (car xs) (car ys))
       (sublist-equal? (cdr xs) (cdr ys)))
      (else #f)))
  (cond
    ((null? xs) #t)
    ((null? ys) #f)
    ((sublist-equal? xs ys) #t)
    (else (sublist? xs (cdr ys)))))

注意内部 sublist-equal? 辅助函数。

我还使用 cond 而不是嵌套的 if 表达式，因为在这种情况下 cond 应该真正用于表示这种逻辑。此外，我使用 equal? 而不是 =，因为它是我所知道的大多数方案，= 用于数字比较（你的可能不同，我不知道）。

Answer 2

这是我的版本 "without a helper function"。不过，它确实使用了两个嵌套循环：

(define (sublist? needle haystack)
  (if (null? needle)
      #t
      (let ((first (car needle)))
        (let outer ((cur haystack))
          (define (next)
            (outer (cdr cur)))
          (cond ((null? cur) #f)
                ((eqv? (car cur) first)
                 (let inner ((lhs (cdr needle))
                             (rhs (cdr cur)))
                   (cond ((null? lhs) #t)
                         ((null? rhs) (next))
                         ((eqv? (car lhs) (car rhs))
                          (inner (cdr lhs) (cdr rhs)))
                         (else (next)))))
                (else (next)))))))

Answer 3

(define sublist? (xs ys)
  (cond ((= xs '()) #t)  ;;cond easier to read than 
        ((= ys '()) #f)  ;;nested if statements
        ((and (= (car xs) (car ys)) 
 ;;need to check for more than singleton match
              (or (null? (cdr xs))
                  (and (not (null? (cdr ys)))
                       (= (cadr xs) (cadr ys))
                       (sublist? (cdr xs) (cdr ys)))))) ;not tail call
  ;;this cond clause has no second part, 
  ;;the first will return #t or #f
  ;;will backtrack if #f is propagated up the stack.
         (else (sublist? xs (cdr ys)))) ; tail call

递归子列表？功能

Recursive sublist? function

scheme