Как я могу получить все возможные комбинации наборов и подмножеств списка, которые удовлетворяют условиям с Common Lisp

Question

Для списка элементов для L = (A B C D), чтобы сгенерировать все возможные комбинации элементов, которые удовлетворяют лексикографическому порядку элементов (A

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)

Чтобы получить именно ваш вывод описаний, вы можете удалить 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))