lisp - 检查适当的子集

Question

我需要一个函数来检查列表 a 是否是列表 b 的真子集。到目前为止我的代码是:

(defun proper-subset (a b)
    (cond
    (( or (null b)(null b)) nil)
    ((equal a b) nil)
    ((find (car a) b) (proper-subset (cdr a) b))
   )
)

find 检查 a 的每个元素是否在 b 中。我知道空参数也需要一些工作，但我试图弄清楚如何确定何时在 b 和 b< 中找到 a 的每个元素 有另一个元素。有内置函数可以使这更容易，但这是一个家庭作业问题，所以我必须自己写。任何提示或建议将不胜感激。

Answer 1

Common Lisp 定义了许多函数来将列表作为集合处理，因此您无需编写自己的函数。特别是，有用的功能出现在 The Conses Dictionary 的底部。 .特别有用的是

• set-difference , nset-difference
• set-exclusive-or , nset-exclusive-or
• subsetp
• union , nunion

subsetp 几乎 做你想做的，但它正在检查不正确的子集。但是，请注意您可以使用这些函数来计算您需要的内容。最直接的方法是检查 A 是否是 B 的子集，以及是否 B - A ≠ {}。这符合您的描述，“a 的每个元素都在 b 中找到并且 b 有另一个元素”。

(defun proper-subsetp (a b)
  (and (subsetp a b)                       ; every element of a is found in b
       (not (endp (set-difference b a))))) ; b has another element

CL-USER> (proper-subsetp '(1 2 3) '(1 2 3 4))
T
CL-USER> (proper-subsetp '(1 2 3 4) '(1 2 3 4))
NIL

因为这些函数实际上采用了一些参数来让您确定如何比较元素。您可以使用 &rest 参数添加这些并应用:

(defun proper-subsetp (a b &rest keys)
  (and (apply 'subsetp a b keys )
       (not (endp (apply 'set-difference b a keys)))))

使用它，您可以比较它们的长度，而不是直接比较元素:

CL-USER> (proper-subsetp '("a" "bb" "ccc") '("1" "22" "333") :key 'length)
NIL
CL-USER> (proper-subsetp '("a" "bb" "ccc") '("1" "22" "333" "4444") :key 'length)
T