Статьи / Задачи с решениями - часть вторая (Задача №3: Равенство множеств)
В статье рассматривается 7 задач и предлагаются детали реализации.
Автор: Потапенко В.А.
Написал: artish   Дата: 2008-09-09 20:10
Комментарии: (0)   Рейтинг:
Задача: Равенство множеств

Реализовать предикат равенства множеств

Определения:

Через обозначается отношение принадлежности, т.е. x A означает, что элемент x принадлежит множеству A . В противном случае пишут x A.

Два множества A и B называются равными, если они состоят из одних и тех же элементов. В этом случае пишут A = B.

Задача перекликается с первой задачей. На основе построенного решения можно получить обобщенный предикат принадлежности. Мы останемся в рамках описанного представления множеств.

Проведем анализ задачи. Задача состоит в написании предиката universal-equivalence~ от двух аргументов a и b.

Два множества эквивалентны тогда и только тогда, когда каждый из элементов одного множества принадлежит другому.

Боюсь, что это не самое лучшее определение для реализации. Так как порождает полный перебор. Полный перебор в данной ситуации можно выразить с помощью композиции mapcar~:
 
(defun s-eq-predicate (s1 s2)
(cond
((null s2) (null s1))
((null s1) (null s2))
((atom s1) (eq s1 s2))
((atom s2) (eq s2 s1))
((eval (cons 'and (mapcar~
#'(lambda (x) (eval (cons 'or (mapcar~
#'(lambda (y) (s-eq-predicate x y))
s2 ))))
s1 )))
(eval (cons 'and (mapcar~
#'(lambda (x) (eval (cons 'or (mapcar~
#'(lambda (y) (s-eq-predicate x y))
s1 ))))
s2 )))
)
(t nil)
)
)
 

Тестирование:
 
> (s-eq-predicate '(a (b)) '(b a))
NIL
> (s-eq-predicate '(a (b)) '((b) a))
T
> (s-eq-predicate '(a (b)) '((b) a b))
NIL
> (s-eq-predicate '(a b (b)) '((b) a b))
T
> (s-eq-predicate '(a b (b)) '((b c) a b))
NIL
> (s-eq-predicate '(a b (c b)) '((b c) a b))
T
> (s-eq-predicate '((a b) (b c)) '((c b) (b a)))
T
> (s-eq-predicate '(a ((b a) a)) '(((a b) a) a))
T
 

Перейдем к решению следующей задачи.

На основе предиката s-eq-predicate легко обобщить in-predicate так, чтобы он работал для любых двух s-выражений. А значит реализовать задачу 1 в полном объеме.
[1] [2] > 3 < [4] [5] [6] [7]


Онлайн :

0 пользователь(ей), 31 гость(ей) :




Реклама на сайте: