1

假设我有两个相同但顺序不同的 lisp 列表：'(A B C)和 ' (C B A)。我如何检查它们是否相同（在元素相同的意义上）？

CL-USER> (equal '(a b c) '(c b a))
NIL
4

5 回答 5

7

像这样：

  (not (set-exclusive-or '(a b c) '(c b a)))

T如果两个集合相等则返回，否则返回 NIL。

[编辑]如果它们不是真正的集合，那么你可以使用这个：

  (not (set-exclusive-or 
         (remove-duplicates '(a b c))
         (remove-duplicates '(c b a))))
于 2013-04-25T23:55:09.290 回答
3

如果列表不是集合并且重复项很重要，则可以使用如下函数：

(defun same-elements-p (a b)
  (loop (when (and (null a) (null b)) 
          (return t))
        (when (or (null a) (null b))
          (return nil))
        (setf b (remove (pop a) b :count 1))))

如果两个列表都是空的，它们是相同的。我们从另一个列表中删除一个列表的所有项目，看看会发生什么。注意 的:count 1论点REMOVE。它确保只删除一项。

于 2013-04-26T06:37:46.100 回答
1

我们可以定义类似于 EQUAL 和 EQUALP 的函数perm-equal，perm-equalp除了如果参数是列表，那么它们的排列无关紧要。清单(1 1 2 3)是perm-equalto (2 1 3 1)，但不是 to (2 3 1)。

该实现通过排序将值标准化为规范排列。这带来了需要进行不等式比较的丑陋幽灵。但是，我们可以通过提供一个适用于数字、符号和字符串的预定义来隐藏它。（为什么sort函数不做这样的事情，方式eql默认为:key参数？）

(defun less (a b)
  (if (realp a)
    (< a b)
    (string< a b)))

(defun lessp (a b)
  (if (realp a)
    (< a b)
    (string-lessp a b)))

(defun perm-equal (a b &optional (pred #'less))
  (if (or (atom a) (atom b))
    (equal a b)
    (let ((as (sort (copy-list a) pred))
          (bs (sort (copy-list b) pred)))
      (equal as bs))))

(defun perm-equalp (a b &optional (pred #'lessp))
  (if (or (atom a) (atom b))
    (equalp a b)
    (let ((as (sort (copy-list a) pred))
          (bs (sort (copy-list b) pred)))
      (equalp as bs))))

笔记：

  • 不处理不正确的列表：它只是尝试对它们进行排序，然后游戏就结束了。
  • 即使equalp比较向量，perm-equalp也不会将其置换压缩逻辑扩展到向量。
  • realp用于测试数字，因为复数满足numberp，但不能与 比较<。
于 2013-04-26T18:32:15.753 回答
1

非集合的简单答案是对两个列表进行排序。CL 的默认排序是破坏性的，因此如果您想在之后保留它们，您将需要副本。

(defun sorted (a-list predicate)
  (sort (copy-list a-list) predicate))

(defun same-list-p (list-a list-b predicate)
  (equalp (sorted list-a predicate) (sorted list-b predicate)))

它没有最好的性能，但简单而实用。

于 2013-04-26T18:55:48.627 回答
0

这在我看来就像一个 O(n) 变体：

(defun equal-elementwise (a b &key (test #'eq))
  (loop with hash = (make-hash-table :test test)
     for i on a for j on b do
       (let ((i (car i)) (j (car j)))
         (unless (funcall test i j)
           (setf (gethash i hash) (1+ (gethash i hash 0))
                 (gethash j hash) (1- (gethash j hash 0)))))
     finally (return
               (unless (or (cdr i) (cdr j))
                 (loop for value being the hash-value of hash do
                      (unless (zerop value) (return))
                    finally (return t))))))

但是，这在短名单上效率不高。

于 2013-04-26T07:22:26.537 回答