Классы эквивалентности 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))