CODEWITHSUNDEEP
listsetsubsetracketsublist
terrylt1
terrylt1

Reputation: 67

How to find sets containing sets in Racket

So I have this program that has several definitions. Three of interest here are (set-equal? L1 L2), (union S1 S2) and (intersect S1 S2).

For set-equal? it should test if L1 and L2 are equal, where Two sets are equal if they contain exactly the same members, ignoring ordering so if the following is called: (set-equal? '(1 (2 3)) '((3 2) 1)), it should return true. However when I run my program on the above call returns false.

union of two sets is the set of all elements that appear in either set with no repetitions. So when the following is called: (union '((1 2 3)) '((3 2 1))), it should return ((1 2 3)). However when I run my program the on above call returns ((1 2 3) (3 2 1).

intersect of two sets is the set of elements that appear in both sets. So when the following is called: (intersect '((1 2 3)) '((3 2 1))), it should return ((1 2 3)). However when I run my program on the above call it returns ().

Some of my other test cases do work as intended. However, not all, therefore, the program is not quite correct. I am really new to Racket, and find it a bit confusing. I am not sure quite how to resolve the issues mentioned. I am thinking perhaps I need another helper function, but what would it do? And more importantly, how?

My problem seems to be when sets contain other sets, and that is what I am not sure exactly how to deal with.

The code is below.

; 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))
        )))

I appreciate all your help. Thank you

Upvotes: 1

Views: 1059

Answers (2)

Alex Knauth
Alex Knauth

Reputation: 8373

Your definition of set-equal? uses subset? in both directions, that's fine. Your definition of subset? uses member? between an element and a set, that's fine.

But your definition of member? uses eq? between elements, even when those elements could be sets (lists with different orderings). If you intend those sets to be equivalent, you'll need to stop using eq?, and define a new function on nested sets of numbers.

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

Two NestedNumberSets are equal according to nested-number-set=? if they are both numbers and they're =, or if they are both sets and they're 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]))

Then if you replace your uses of eq? with uses of nested-number-set=?, you should get the nested-set-equality behavior you want.

P.S. Until you learn more, I would advise you to stop relying on eq? in your code. It's basically nothing more than pointer equality, so even (eq? (list 1 2) (list 1 2)) returns #false.

Upvotes: 3

tjorchrt
tjorchrt

Reputation: 702

Define like this is easy.

(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 '()) ; '()

In set-equal? we check length of list equal or not. If not equal it obvious not same set.

If two set have same length but they are different set. Before union we certainty get longer set.

(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

It you really expect (set-equal? '(1 (2 3)) '((3 2) 1)) return #ture. And (set-equal? '(1 (2 (3 4))) '(((3 4) 2) 1)) return #ture. In every layer works. Good luck.

Upvotes: 1

Related Questions