How to tell if two sets are equal in content (disregarding order) in racket?

Question

I have a homework problem that is asking me to tell if two sets are equal in content, regardless of order.

Ex: (set-equal? (list 1 2 3) (list 3 2 1)) is true

I have gotten this code so far,

(define (set-equal? list1 list2)
  (cond
    [(and (empty? list1) (empty? list2)) true]
    [(and (cons? list1) (empty? list2)) false]
    [(and (empty? list1) (cons? list2)) false]
    [(and (cons? list1) (cons? list2))
      (if (member? (first list1) list2) 
          (set-equal? (rest list1) list2)
          (set-equal? (rest list1) list2))]))

This code obviously doesn't work because even if two lists are equal, the recursion will lead to (empty) for list 1 and list 2 will still have data, making the final output false.

I think I should approach this way: Check the data in list1 against data in list2 and if there are equal data, remove it from both lists. Then keep checking until either both lists are empty (giving true) or one is empty and one still has data (outputting false). The problem is, I don't know how to code this.

Can anyone give me a little hint on how to fix this problem?

Protract

Answer 1

Assumptions

1. The lists actually represent sets in that they have no duplicate members.

Dead Simple Solution

#lang racket

(define a '(1 2 3))
(define b '(3 2 1))
(define c '(1))

(define (set-equal? a b)
  (equal? (list->set a)
          (list->set b)))

Usage

eq-sets.rkt> (set-equal? a b)
#t
eq-sets.rkt> (set-equal? a c)
#f
eq-sets.rkt> (set-equal? a a)
#t

A Listy Approach

This isn't very elegant or very efficient in terms of running time, but it shows a lambda and how the function just needs to return the result of evaluating a boolean expression:

(define (set-equal2? a b)
  (and (= (length a)
          (length b))
       (not (false?
         (andmap
          (lambda (e) (member e b))
          a)))))

Notes

1. and short circuits if the lengths are unequal.

2. (not (false? (andmap... is used to return #t rather than a value that evaluates to #t for example (set-equal?2 a a) would return '(1 2 3) instead of #t without it because that's how andmap works. Whether it is worth going through the ceremony of (not (false? ... depends on how you feel about types.

Histochemistry

Answer 2

Recall the mathematical definition of what it means for a set A to be subset of B.

     A is a subset of B 
<=>  for all a in A :  a is a member of B

The mathematical definition can be written in Racket like this:

(define (subset? A B)
  (for/and ([a A])
    (member a B)))

The definition of equality between two sets A and B is:

     A = B
<=>  A is a subset of B  and  B is a subset of A

The Racket version is:

(define (set-equal? A B)
  (and (subset A B)
       (subset B A)))

However for finite sets we can do better (in terms of speed):

For finite sets:
     A = B
<=>  A is a subset of B  and   size(A) = size(B)

And in Racket:

(define (set-equal? A B)
  (and (= (length A) (length B))
       (subset? A B)))

Vinita

Answer 3

Is there a stipulation that you have to use recursion? If not you can do the following:

If they're of unequal length, then the result is false. There's no need to proceed any further in this case. And, we know that and(expr..) will return false as soon as it finds a false expression going to left to right.

From the documentation:

(and expr ...) 

If no exprs are provided, then result is #t.

If a single expr is provided, then it is in tail position, so the results of the and expression are the results of the expr.

Otherwise, the first expr is evaluated. If it produces #f, the result of the and expression is #f. Otherwise, the result is the same as an and expression with the remaining exprs in tail position with respect to the original and form.

Given that they're of equal length, sort the input lists in ascending (or descending as long as they're both sorted the same way) and check if they're equal.

(define (set-equal? list1 list2)
  (and (equal? (length list1) (length list2)) (equal? (sort list1 <) (sort list2 <)))
)

(set-equal? (list 1 2 3) (list 3 2 1))
(set-equal? (list 2 1 2) (list 1 2 2))
(set-equal? (list 2 1 2) (list 7 2 2))

output: true true false

Islander

Answer 4

Racket allows you to write procedures as if you were writing mathematical expressions. The math expression for 2 sets being equal could go as follows:

Two sets A and B are equal if for each x in A, there is x B.

Thus, first you need to write a procedure that tells you whether an item is part of a set.

;procedure in? : Tells if an element x is in set S.
;If S is empty, then x is not in it, 
;if the first element of S is eq. to x then x is in it. 
;otherwise, check with next element.
(define in? 
    (lambda (x S) 
      (cond ((empty? S) #f)
            ((equal? (car S) x) #t)
            (else (in? x (cdr S)))
      )))

Now we can use that procedure to tell if two lists are equal.

;procedure equal-sets? : Tells if 2 sets are equal.
;Uses andmap as a for-each loop.
(define equal-sets?
    (lambda (A B)
         (andmap (lambda (x) (in? x B)) A) ) )

Let us know of any doubt!

Cad

Answer 5

Ben Rudgers' solution with list->set is the best.

But we can fix solution from question with minimal changes:

(define (set-equal? list1 list2)
  (cond
    [(and (empty? list1) (empty? list2)) true]
    [(and (cons? list1) (empty? list2)) false]
    [(and (empty? list1) (cons? list2)) false]
    [(and (cons? list1) (cons? list2))
      (if (member (first list1) list2) 
          ; compare rest of list1 with rest of list2
          (set-equal? (rest list1) (remove (first list1) list2))
          ; if (first list1) is not a member of list2 then they are not equal
          #f)]))

Now it works but we can better:

(define (set-equal? list1 list2)
  (cond
    [(and (empty? list1) (empty? list2)) true]
    [(and (cons? list1) (empty? list2)) false]
    [(and (empty? list1) (cons? list2)) false]
    [else ; the last condition always true when first 3 are not
      (and (member (first list1) list2) 
           (set-equal? (rest list1) 
                       (remove (first list1) list2)))]))

And now we can drop some conditions and replace cond by if:

(define (set-equal? list1 list2)
  (if (empty? list1)
      (empty? list2)
      (and (member (first list1) list2) 
           (set-equal? (rest list1)
                       (remove (first list1) list2)))))

Note: don't use this in real projects due to poor performance.

Flagwaving