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?

Answer 1

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

Answer 2

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.

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