0

我有一个问题：我需要查找列表是否等于第二个，例如：

(set%eq? '(1 2 3) '(1 2 3))     ===> #t

(set%eq? '(1 2 3) '(2 3 4))     ===> #f

这些例子在我的程序中是正确的，但这个不是：

(set%eq? (quote ((quote one) (quote two) (quote three))) (quote ((quote one) (quote two) 
(quote three))))    ====> #f but i need #t

怎么了？这是我的程序：

(define (set-eq? xs ys) 

(cond ((and (null? xs) (null? ys)) #t) 
       ((null? ys) #f) 
       ((eq? (car xs) (car ys)) (set-eq? (cdr xs) (cdr ys)))
       ((eq? (car xs) (car (reverse ys))) (set-eq? (cdr xs) (cdr (reverse ys))))
       (else #f)))
4

2 回答 2

0

发布的代码中有几个错误，仅供参考，该程序测试两个列表是否相等，它并不是真正测试两组之间的相等性：

(define (set-eq? xs ys)
  (cond ((and (null? xs) (null? ys)) #t)
        ((or (null? xs) (null? ys))  #f) ; missing case
        ((equal? (car xs) (car ys)) (set-eq? (cdr xs) (cdr ys))) ; use equal?
        ; deleted unnecessary case here. Anyway, why are you reversing the list?
        (else #f)))

现在这将起作用：

(set-eq? '(1 2 3) '(1 2 3))
=> #t

(set-eq? '(1 2 3) '(2 3 4))
=> #f

(set-eq? (quote ((quote one) (quote two) (quote three)))
         (quote ((quote one) (quote two) (quote three))))
=> #t

事实上，这也可以：

(equal? '(1 2 3) '(1 2 3))
=> #t

(equal? '(1 2 3) '(2 3 4))
=> #f

(equal? (quote ((quote one) (quote two) (quote three)))
        (quote ((quote one) (quote two) (quote three))))
=> #t

...但这不起作用，列表明显不同：

(set-eq? '(1 2 3 4) '(4 1 2 3)) 
=> #f

如果您打算测试两组之间的相等性，则必须完全重新考虑算法。这里有个思路：写一个subset?程序，测试一个列表是否是另一个列表的子集（即：一个列表中的所有元素是否都包含在另一个列表中），然后测试是否(and (subset? l1 l2) (subset? l2 l1))为真，如果发生，那么他们'根据相等的集合定义相等。

于 2013-10-11T19:08:17.317 回答
0

根据 OP 的评论，很明显这些是set-eq?

(set-eq? '(a b c) '(c b a)) ; ==> #t
(set-eq? '(a b c) '(b c a)) ; ==> #t
(set-eq? '() '())           ; ==> #t
(set-eq? '(a b) '(a b c))   ; ==> #f
(set-eq? '(a b c) '(a c))   ; ==> #f

如果列表没有重复项，则可以迭代第一个列表并尝试在第二个列表中找到它。如果找到，我们将使用没有匹配的两个列表进行递归。

#!r6rs
(import (rnrs)
        (rnrs lists))

(define (set-eq? xs ys)
  (if (null? xs) 
      (null? ys) ; #t if both sets are empty, otherwise #f
      (let ((cur (car xs)))        
        (and (memq cur ys) ; first element is found 
             (set-eq? <??> (remq <??> <??>)))))) ; recurse without first in both lists

有一些方法可以更快地做到这一点。Eq 散列第一个列表并迭代第二个。如果所有匹配并且hashtable-size与迭代次数相同，则为#t。

于 2013-10-11T20:29:49.480 回答