Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LISP: How can I test if two lists have the same elements?

I want to write a function that takes as parameters two lists and checks if every element in the first one is included in the second ( the order of the elements doesn't matter). The function will also be checking if the two list have the same length (the two list can't have duplicate elements) because if not then the function will return nill/false.

For example: (A B C D E F) and (B E A F D C) have the same elements (nil) and (nil) have the same elements

(A B C D E F) and (A B C D E F G) don't have the same elements

The problem is that I know only some basic commands and I can use just those ones. These are almost all the commands that I know:

CAR, CDR, LENGTH, NULL, MEMBER, NOT, AND, OR, NOT, MAPCAR, APPLY, DO, SETQ, LET

I wrote the following function up until now, but I don't know how to check for duplicate members and it doesn't work properly for all the lists that I want to check:

(defun same-elem-p (lst1 lst2)
  (cond ((not (null lst1))
         (cond ((member (car lst1) lst2)
                (same-elem-p (cdr lst1) lst2))
               (t nil)))
        (t t))) 

I hope I explained the problem well enough.

like image 535
seby598 Avatar asked Apr 02 '13 09:04

seby598


2 Answers

You can define a function that returns true when a list contains another one :

(defun member (x liste) 
   (cond
      ((null liste) ()) 
      ((equal (car liste) x) liste) 
      (t (member x (cdr liste))))) 

(defun inclus (liste1 liste2) 
   (cond 
      ((null liste1) t) 
      ((member (car liste1) liste2)(inclus (cdr liste1) liste2)) 
      (t ()))) 

Then use it to determine whether the two lists are equal :

(defun compare (liste1 liste2)
   (if ((and (inclus liste1 liste2) (inclus liste2 liste1)))
      (print "the 2 lists are equivalent")
      (print "the 2 lists aren't equivalent"))) 
like image 120
Kira Avatar answered Sep 19 '22 22:09

Kira


Two lists have the same elements when each element in one list is a member of the other list, and vice-versa. Assuming you can use the every function, a quick way to test this is the following:

(defun same-elements (lst1 lst2)
  (and (= (length lst1) (length lst2))
       (every #'(lambda (x) (member x lst2))
                lst1)
       (every #'(lambda (x) (member x lst1))
                lst2)))

For instance:

CL-USER> (same-elements '(a b c) '(c a b))
T

Note that this code will not handle every circumstance. For instance, it would return T when two different elements are repeated in the two lists, as in (a b b c) and (a a b c). But, for the most part, it does its job.

like image 45
Andrea S. Avatar answered Sep 19 '22 22:09

Andrea S.