A function to compare sets; help improving efficie

问题:

I am attempting to write a function which compares two lists to see if they represent the same set. That is '(a b c d d) and '(d c b a d) represent the same set. The elements can be in any order.

This is what I have, which works:

(defun samesetp (list1 list2)
  (cond
    ((null list1) (null list2))
    ((eq list2 (remove (car list1) list2 :count 1)) nil)
    (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))))

The reason I do not like this is that (remove (car list1) list2 :count 1)) is being computed twice - once to test if the remove operation truly removed anything, and once to recursively test the rest of the list(s) sans that element.

Can anyone suggest a way to improve this without using a different algorithm?

回答1:

(defun samesetp (list1 list2)
    (cond
        ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))
    )
)

First let's format it correctly:

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1)))))

If you use a form twice and you want to change that, then you need to store a value. LET is the construct for that. If it doesn't fit into one COND, then you need a second one.

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((eq list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

Now, EQ can't be used to compare lists. Use EQUAL.

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((equal list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

COND is overkill here, use IF:

(defun samesetp (list1 list2)
  (if (null list1)
      (null list2)
    (let ((list3 (remove (car list1) list2 :count 1)))
      (if (equal list2 list3)
          nil
        (samesetP (cdr list1) list3)))))

Now, you only need to make the function do what was asked in the homework. But it is your homework anyway.

回答2:

I guess you are not allowed to use built-in functions for solving the problem, but just to note there is one:

(set-difference list1 list2)