如何在Racket中查找包含集合的集合

Question

所以我有这个程序，它有几个定义。这里感兴趣的三个是(集等于？L1 L2(、(并集S1 S2(和(相交S1 S2(。

是否设置为相等？它应该测试L1和L2是否相等，其中如果两个集合包含完全相同的成员，则两个集合相等，如果调用以下内容，则忽略排序：(设置为等于？'(1(2 3(('((3 2(1((，则应返回true。但是，当我在上面的调用中运行程序时，返回false。

两个集合的并集是所有元素的集合，这些元素出现在任意一个集合中，没有重复。因此，当调用以下命令时：(并集"((1 2 3(("((3 2 1((，则应返回((1 3((。然而，当我运行我的程序时，上面的调用返回((1 2 3((3 2 1(。

两个集合的交集是出现在两个集合中的元素集。因此，当调用以下命令时：(与"((1 2 3(("((3 2 1((相交，则应返回((1 3((。但是，当我在上面的调用中运行程序时，它会返回((。

我的其他一些测试用例确实按预期工作。然而，并不是所有的，因此，该程序并不完全正确。我对拉基特真的很陌生，觉得有点困惑。我不太清楚如何解决上述问题。我想也许我需要另一个助手功能，但它能做什么？更重要的是，如何？

我的问题似乎是当集合包含其他集合时，而这正是我不确定如何处理的问题。

代码如下。

; Tests if x is in L where L is a set, represented as a list
(define (member? x L)
(if (null? L)
#f
(cond
[(eq? x (car L)) #t]
(else (member? x (cdr L))
))))
; Test whether L1 is a subset of L2
(define (subset? L1 L2)
(if (null? L1)
#t
(and (member? (car L1) L2)
(subset? (cdr L1) L2)
)))
; Test whether L1 and L2 are equal
(define (set-equal? L1 L2)
(and (subset? L1 L2)
(subset? L2 L1)
))
; Join two sets together
(define (union S1 S2)
(if (null? S1)
S2
(cond
[(member? (car S1)S2) (union (cdr S1)S2)]
(else (cons (car S1) (union (cdr S1)S2)))
)))
; Return the intersection of two sets
(define (intersect S1 S2)
(if (null? S1)
'()
(cond
[(member? (car S1)S2)
(cons (car S1) (intersect (cdr S1)S2))]
(else (intersect(cdr S1)S2))
)))

我感谢你的帮助。谢谢

Answer 1

您对set-equal?的定义在两个方向上都使用subset?，这很好。subset?的定义在元素和集合之间使用member?，这很好。

但是member?的定义在元素之间使用eq?，即使这些元素可以是集合(具有不同顺序的列表(。如果您希望这些集合是等价的，则需要停止使用eq?，并在嵌套的数字集上定义一个新函数。

;; A NestedNumberSet is one of:
;;  - Number
;;  - [Listof NestedNumberSet]
;; where order doesn't matter in the lists

根据nested-number-set=?，如果两个NestedNumberSet都是数字并且它们是=，或者如果它们都是集合并且它们是set-equal?，则它们是相等的。

;; nested-number-set=? : NestedNumberSet NestedNumberSet -> Boolean
(define (nested-number-set=? a b)
(cond [(and (number? a) (number? b)) (= a b)]
[(and (list? a) (list? b))     (set-equal? a b)]
[else                          #false]))

然后，如果将eq?的使用替换为nested-number-set=?的使用，则应该获得所需的嵌套集相等行为。

---

p.S.在您了解更多信息之前，我建议您停止在代码中依赖eq?。它基本上只不过是指针相等，所以即使是(eq? (list 1 2) (list 1 2))也会返回#false。

Answer 2

这样定义很容易。

(set-equal? '(1 (2 3)) '((2 3) 1))返回#true

(set-equal? '(1 (2 3)) '((3 2) 1))返回#false

#lang racket
(define s1 '(1 2 3 4 5 6))
(define s2 '(1 2 3 7 8 9))
(define (union S1 S2)
(remove-duplicates (append S2 S1)))
(union s2 s1) ; '(1 2 3 4 5 6 7 8 9)
(union '() '()) ; '()

(define (intersect S1 S2)
; just like (if '() #t #f) -> #t
(filter (lambda (e) (member e S2)) S1))
;;; TEST
(intersect s1 s2) ; '(1 2 3)
(intersect s1 '()) ; '()

在set-equal?中，我们检查列表的length是否相等。若不相等，那个么显然不是同一集合。

若两个集合具有相同的长度，但它们是不同的集合。在union之前，我们肯定会得到更长的集合。

(define (set-equal? S1 S2)
(let ([c1 (length S1)]
[c2 (length S2)]
[c1^c2 (length (union S1 S2))])
(if (= c1 c2) (= c1 c1^c2) #f)))
;;; TEST
(set-equal? (union s1 s2) (union s2 s1)) ; #t
(set-equal? (union '() s1) s1) ; #t
(set-equal? '() '()) ; #t
(set-equal? '(1 (2 3)) '((2 3) 1)) ; #t
(set-equal? '(1 (1)) '((1) 1)) ; #t
(set-equal? '(1 (2 3)) '((3 2) 1)) ; #f
(set-equal? s1 s2) ; #f
(set-equal? '(1 2) '()) ; #f

如果您真的期望(set-equal? '(1 (2 3)) '((3 2) 1))返回#ture。CCD_ 26返回CCD_。在每一层工作。祝你好运