我如何获得满足 Common Lisp 条件的列表的集合和子集的所有可能组合

Question

对于 L = (A B C D) 的元素列表，要生成满足元素字典顺序 (A < B < C < D ...< Z) 的所有可能的元素组合，将生成所有组合。例如 L = (A B C D) 井输出 (A), (B), (C), (D), (A B), (B C), (C D), (A B C), (B C D), (A B C D).

Answer 1

看起来你只是写了一个简单的函数来获取列表的幂集，然后删除一个空集，然后以任何你想要的方式对其进行排序。

(defun powerset (lst)
  (if lst (mapcan (lambda (el) (list (cons (car lst) el) el))
                (powerset (cdr lst)))
      '(())))

CL-USER> (powerset '(A B C D))
((A B C D) (B C D) (A C D) (C D) (A B D) (B D) (A D) (D) (A B C) (B C) (A C)
 (C) (A B) (B) (A) NIL)

要获得准确的描述输出，您可以删除 NIL 并将其反转：

CL-USER> (reverse (remove nil (powerset '(A B C D))))
((A) (B) (A B) (C) (A C) (B C) (A B C) (D) (A D) (B D) (A B D) (C D) (A C D)
 (B C D) (A B C D))

这是你想要的吗？

更新。抱歉，没有提到您希望它以另一种方式排序。你应该求助于它：

CL-USER> (sort 
           (reverse
             (remove nil
                     (powerset '(A B C D))))
             #'< :key #'length)
((A) (B) (C) (D) (A B) (A C) (B C) (A D) (B D) (C D) (A B C) (A B D) (A C D)
 (B C D) (A B C D))

这是另一个更重要的解决方案，使用 loop 宏，执行您描述的操作：

(defun combinations (lst)
  (loop :for i :below (expt 2 (length lst))
        :when (loop :for j :below i :for el :in lst if (logbitp j i) :collect el)
        :collect it :into result
        :finally (return (sort result #'< :key #'length))))

CL-USER> (combinations '(A B C D E)) 
((A) (B) (C) (D) (E) (A B) (A C) (B C) (A D) (B D) (C D) (A E) (B E) (C E)
 (D E) (A B C) (A B D) (A C D) (B C D) (A B E) (A C E) (B C E) (A D E) (B D E)
 (C D E) (A B C D) (A B C E) (A B D E) (A C D E) (B C D E) (A B C D E))

Answer 2

lexicographical（非词典）顺序可以通过以下函数获得，该函数检查列表 a 是否在词典顺序中位于列表 b 之前：

(defun lex<= (a b)
  (or (null a)
      (and b 
           (string<= (car a) (car b))
           (lex<= (cdr a) (cdr b)))))

所以，你可以产生所有的组合，就像在 coredump 的答案中一样，然后用 (sort result #'lex<=).

对它们进行排序

我如何获得满足 Common Lisp 条件的列表的集合和子集的所有可能组合

How can i get all possible combinations of sets and subsets of a list that satisfy conditions with Common Lisp

lisp

clisp

common-lisp