Классы эквивалентности Lisp

Question

Мне нужно написать программу для классов эквивалентности и получить эти выходы ...

(equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
 => ((a b c g h) (d e f))

(equiv '((a b) (c d) (e f) (f g) (a e)))
 => ((a b e f g) (c d))

По сути, набор - это список, в котором порядок не имеет значения, но элементы не появляются более одного раза. Функция должна принять список пар (элементы, которые связаны в соответствии с некоторым отношением эквивалентности), и вернуть набор классов эквивалентности без использования итерационных операторов (например, do, set!, и т.д.).

Однако установить утилиты, такие как set-intersection, set-union и функция, которая устраняет дубликаты в списке и встроенных функциях union, intersection, и remove-duplicates разрешены.

Большое спасибо!

Кстати, это не вопрос домашнего задания. Мой друг нуждается в этом кусочке кода, чтобы решить Smylare -вопросы.

Answer 1

Это звучит как типичный домашнее задание.

Это не так сложно, хотя.

Простая рекурсивная функция по списку ввода подойдет. Ингредиенты функции уже упоминаются в описании задачи: Простые операции набора.

Если это домашняя работа, то это применяется: типичная стратегия для домашних заданий заключается в том, что вам нужно сначала показать свою попытку решения. Это должно быть, по крайней мере, в основном правильной формулировкой алгоритма или почти рабочего кода. Тогда лисперы могут помочь вам с последними штрихами ...

Ну, время проходит и нет решения.

Итак, вот один использует обыкновенный LISP:

Нам нужны три функции.

Первая функция добавляет одну пару к набору пар. Пара - это список. Набор пар - это список пар. Для пары мы вычисляем два набора: набор пар, которые эквивалентны, и набор пар, которые не являются эквивалентными. Мы объединяем пары, которые эквивалентны нашей входной паре в один набор.

(defun equiv-add (e l)
  (let ((l- (remove-if     (lambda (i) (intersection e i)) l))
        (l+ (remove-if-not (lambda (i) (intersection e i)) l)))
    (cons (remove-duplicates (reduce #'union (cons e l+)))
          l-)))

Вторая функция добавляет каждую пару набора пар к результату. Это добавляет их, позвонив в эквивалент.

(defun equiv-aux (list result)
  (if (null list)
      result
    (equiv-aux (rest list)
               (equiv-add (first list)
                          result))))

Третья функция просто вызывает эквива-о-входной набор и пустым результатом. Кроме того, это сортирует сублисты результата.

(defun equiv (list)
  (mapcar (lambda (el)
            (sort el #'string-lessp))
          (equiv-aux list '())))

Пример вызовов:

CL-USER 34 > (equiv '((a b) (c d) (e f) (f g) (a e)))
((A B E F G) (C D))

CL-USER 35 > (equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
((A B C G H) (D E F))