递归子列表?功能 [英] Recursive sublist? function

问题描述

我似乎不知道如何编写一个正确的 uscheme(MIT Scheme 的衍生物)函数，该函数将返回布尔值，无论列表是否包含较小的列表.

I can't seem to figure how to write a correct uscheme (A derivative of MIT Scheme) function that will return boolean whether a list contains a smaller list.

这是我写的.

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

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

It passes most of my test cases except this one test case.

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

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

Test case requires that sublist is consecutive with no random element in between.

我对如何纠正这个问题有点困惑.其他人有什么想法吗?

I'm a bit stuck on how to correct this. Does anyone else have an idea?

推荐答案

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

The problem is that your algorithm is too eager—once it finds two elements that are equal, it immediately throws away that element and keeps checking. In actuality, finding two equal elements is not enough, since your algorithm might have to backtrack if it finds an incomplete match.

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

The easiest way to represent this sort of algorithm would be with a helper function that determines if a sublist matches at a given position in the list. The sublist? function would then iterate through each position in the larger list looking for matches.

这是我的实现:

(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? 辅助函数.

Note the internal sublist-equal? helper function.

我也使用 cond 而不是嵌套的 if 表达式，因为在这种情况下应该真正使用 cond 来表示这种逻辑.此外，我使用 equal? 而不是 =，因为我知道的大多数方案，= 用于数字比较(您的可能不同，我不知道).

I also use cond instead of nested if expressions, since cond should really be used in this case to represent this sort of logic. Furthermore, I use equal? instead of =, since it most Schemes I know of, = is for numeric comparison (yours might be different, I don't know).

这篇关于递归子列表?功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！