list - 方案 - 从列表列表中删除子列表

Question

我有一个列表列表，例如。((x y z) (y z) (x y))，我想知道是否R5RS Scheme有办法从这个列表中只删除子列表：例如。(y z)是一个子列表，因为它已经在 'inside'(x y z))中，在我们的示例中将离开((x y z))。

这可能比我想象的更复杂，但我猜它会使用地图或过滤器，但我不确定你如何以这种方式“清理”整个列表。

Answer 1

这个问题比看起来要棘手一些。我将使用 Racket，因此可能会出现一些非标准功能，但如果您坚持使用基本的 R5RS 程序（如有疑问，请查看文档）。另请注意，我的解决方案更喜欢函数式编程风格，因此会有maps、filters 和其他高阶过程。

首先，我们需要一种方法来测试一个列表是否是另一个列表在任何位置的子列表；我正在使用这篇文章中的想法来生成所有可能的连续子列表：

(define (inits lst)
  (let loop ((acc '())
             (n (length lst)))
    (if (negative? n)
        acc
        (loop (cons (take lst n) acc) (sub1 n)))))

(define (tails lst)
  (let loop ((acc '())
             (n (length lst)))
    (if (negative? n)
        acc
        (loop (cons (drop lst n) acc) (sub1 n)))))

(define (contiguous-sublists lst)
  (cons '()
        (remove* '(())
                 (append-map inits (tails lst)))))

(define (sublist? l1 l2)
  (if (member l1 (contiguous-sublists l2)) #t #f))

现在是实际过程，请注意我假设输入列表是无重复的：

(define (remove-sublists lst)
  (filter
   (lambda (l1)
     (andmap
      (lambda (l2)
        (not (sublist? l1 l2)))
      (remove l1 lst)))
   lst))

它按预期工作：

(remove-sublists '((x y z) (y z) (x y)))
=> '((x y z))