Классы эквивалентности 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 допускаются.

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

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

Answer 1

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

Это не так сложно.

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

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

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

Так вот один с помощью Common 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-))) 

Вторая функция добавляет каждую пару пар пар к результату. Он добавляет их, вызывая EQUIV-ADD.

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

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

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