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

Question

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

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

(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 позволяются.

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

Между прочим, Это не вопрос о домашней работе. Моему другу нужна эта часть кода для решения smilar вопросов.

5

lisp class equivalence

задан bubdada 6 May 2010 в 21:37

1 ответ

Другие вопросы по тегам:

lisp class equivalence

Похожие вопросы:

score 4 · Accepted Answer

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

Однако это не так уж и сложно.

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

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

Ну, время идет, а решения нет.

Вот одно из них с использованием 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 '())))

Example calls:

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