Equivalence Classes

Posted by orcik on Stack Overflow See other posts from Stack Overflow or by orcik
Published on 2010-05-03T14:59:51Z Indexed on 2010/05/04 2:48 UTC
Read the original article Hit count: 306

Filed under:
|
|

I need to write a program for equivalence classes and get this outputs...

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

Basically, A set is a list in which the order doesn't matter, but elements don't appear more than once. The function should accept a list of pairs (elements which are related according to some equivalence relation), and return a set of equivalence classes without using iteration or assignment statements (e.g. do, set!, etc.).

However, set utilities such as set-intersection, set-union and a function which eliminates duplicates in a list and built-in functions union, intersection, and remove-duplicates are allowed.

Thanks a lot!

By the way, It's not a homework question. A friend of mine need this piece of code to solve smilar questions.

© Stack Overflow or respective owner

Related posts about lisp

Related posts about Scheme