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

Question

对于L=（a B C D）的元素列表，要生成满足元素字典顺序（a<B<C<D…<Z）的元素的所有可能组合，将生成所有组合。例如，L＝（A B C D）阱输出（A）、（B）、（C）、（D）、（A B）、。

Answer 1

可以通过以下函数来获得字典顺序（而非字典顺序），该函数检查列表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<=)对它们进行排序。

Answer 2

看起来您只需编写一个简单的函数来获取列表的幂集，然后删除一个空集，并按您想要的任何方式排序。

(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)

要获得确切的describet输出，您可以删除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))