在集合列表中查找所有超集

Question

以下函数的目的是返回集合列表中的所有超集--即删除列表中任何其他集合的子集。(1 2) (12 3) (3 2) (3 5) (5 3) ) -> (1 2 3) (3 5)。有没有一种更优雅、更有效的方法来思考如何做到这一点？这似乎大致符合共同的lisp“减少”模式，但两个不重叠的集合只是简单地缩小到自己。感谢您的任何简化或见解：

(defun supersets (sets)
  (let ((remaining-sets sets))
    (loop for set1 in sets
      do (loop for set2 in (set-difference remaining-sets (list set1))
           when (subsetp set1 set2)
            do (setq remaining-sets
                     (set-difference remaining-sets (list set1)))
               (return))
      finally (return remaining-sets))))

Answer 1

如果问题的定义是(如文章中所述)，

删除列表中任何其他集合的子集。

这将是一个字面实现(我使用了亚历山大的CURRY。如果没有依赖项，可以用常规的LAMBDA替换)：

(defun supersets (sets)
  (remove-if (lambda (set)
               (some (curry #'subsetp set)
                     (remove set sets)))
             sets))

CL-USER> (supersets '((1 2) (1 2 3) (3 2) (3 5) (5 3)))
((1 2 3))

注意，这也从列表中删除了(3 5)，因为它是SUBSETP of (5 3)。如果您想保留它，您可以定义一个考虑相同列表而不是子集的SUBSETP版本。当然，结果中也会有(5 3)。我看不出有(3 5)的逻辑解释，但不包括(5 3)。

编辑:这里还有一个版本，其中一个是(3 5)和(5 3)。

(defun supersets (sets)
  (let ((sets (remove-duplicates sets :test #'set-equal)))
    (remove-if (lambda (set)
                 (some (curry #'subsetp set)
                       (remove set sets)))
               sets)))

另一个编辑:更有效的版本。这样，它就不会不断地用REMOVE创建新的列表。

(defun supersets (sets)
  (remove-if (lambda (set)
               (some (lambda (set2)
                       (unless (eq set set2)
                         (subsetp set set2)))
                     sets))
             sets))

Answer 2

我想这3种功能中的每一种都是有趣的。(不是最好的，而只是在SBCL下得到给定的5组列表的超集( 10M次)。)

davypough (me):  5.7 sec  4.8B cons
Renzo:           3.1      800M
jkiiski          5.0      2.2B

(注:将jkiiski中的前2“删除”改为“删除”。)

如果您不介意后续的问题，如何估计其中一些序列函数的计算复杂性(不需要跳入组装代码，或者进行增加N的实验，并试图识别曲线的形状)？我猜是原始删除-复制是n-平方吗？

Answer 3

@Renzo.太棒了。但是，对于我的应用程序，我需要将您的函数概括为包含:key和:test参数。(超集'( 1 ) (a)) ((12 3) (b)) ((3 2) (c)) ((4 5) (D) ((5 4) (E)：关键#汽车:测试#‘相等) -> (12 3) (b)) ((4 5) (D)。我的尝试不管用。你能明白为什么吗？

(defun supersets (sets &key (key #'identity) (test #'eql))
  (delete-duplicates
    (sort (copy-list sets) 
          #'<= :key #'(lambda (set)
                        (length (funcall key set))))
    :test #'(lambda (set1 set2)
              (subsetp set1 set2 :key key :test test))))

(ps:另外，我注意到，如果我只是在"let“中重新绑定输入”sec“参数(避免了”复制列表“)，那么在最初的示例中执行1000万次的时间就会减少到1秒和0。这是一般原则，还是我离校了？谢谢。