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

Question

所以我有这个程序有几个定义。这里感兴趣的三个是 (set-equal? L1 L2)、(union S1 S2) 和 (intersect S1 S2)。

设置相等？它应该测试 L1 和 L2 是否相等，如果两个集合包含完全相同的成员，则忽略顺序，因此如果调用以下内容，则两个集合相等： (set-equal? '(1 (2 3)) '((3 2) 1))，它应该 return 为真。然而，当我运行我的程序在上面调用时 returns false.

两个集合的并集是出现在任一集合中且没有重复的所有元素的集合。因此，当调用以下内容时： (union '((1 2 3)) '((3 2 1)))，它应该 return ((1 2 3))。然而，当我运行我的程序在上面调用 returns ((1 2 3) (3 2 1).

intersect of two sets 是出现在两个集合中的元素的集合。因此，当调用以下内容时：（相交'（（1 2 3））'（（3 2 1））），它应该return（（1 2 3））。然而，当我运行我的程序在上面调用它 returns ().

我的一些其他测试用例确实按预期工作。但是，并不是所有的，因此，程序不是很正确。我真的是 Racket 的新手，觉得有点困惑。我不太确定如何解决所提到的问题。我在想也许我需要另一个辅助函数，但它会做什么？更重要的是，怎么做？

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

代码如下

; 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? '(1 (2 3)) '((2 3) 1)) return #true

(set-equal? '(1 (2 3)) '((3 2) 1)) return #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))return#ture。并且 (set-equal? '(1 (2 (3 4))) '(((3 4) 2) 1)) return #ture。在每一层工作。祝你好运。

Answer 2

您对 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=? 的使用，您应该会获得所需的 nested-set-equality 行为。

P.S。在您了解更多信息之前，我建议您停止在代码中依赖 eq?。基本上无非就是指针相等，所以连(eq? (list 1 2) (list 1 2))returns#false.

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

How to find sets containing sets in Racket

list

set

subset

sublist

racket