I am trying to create a function in Racket that checks two sets with nested lists and returns true or false. The function is supposed to return true if the numbers match and the lists are the same (regardless of order). I cannot use flattening or merging, the lists and numbers must stay separate from each other.
I can get my function to return the correct answer if the sets only have one nested list, each. However, the problems begin when I try testing for two sets. I have been at this for hours and I have no idea what to do. The code is down below, and the second function (nested-set-equal?) is what I need help with.
#lang racket
;Checks if a set with no nested lists is equal. This one works fine!
(define (set-equal? set1 set2)
(cond
; Base case: If the set lengths are not equal, return '#f'.
[(not (equal? (length set1) (length set2))) #f]
; Base case: If the lengths of both sets are zero, return '#t'.
[(= (length set1) (length set2) 0) #t]
;Recursive case: call the set-equal? function while using the `cdr of set1` and `set2` without the element that matches the `car of set 1` as new parameters.
;If the remove function does not remove a number from set2 after a call, it means the sets do not match and the function ends.
[else (set-equal? (cdr set1) (remove (car set1) set2))]
)
)
;set-nested-equal?: Checks if two sets have the same elements. This function checks nested lists as well.
; Returns: #t if the sets are equal and #f if sets are not equal.
; Parameters:
; set1 (list) - list to compare with set2
; set2 (list) - list to compare with set1
;Define the function 'nested-set-equal?' with two parameters `set1` and `set2`.
(define (nested-set-equal? set1 set2)
(cond
; Base case: If the set lengths are not equal, return '#f'.
[(not (equal? (length set1) (length set2))) #f]
; Base case: If the lengths of both sets are zero, return '#t'.
[(= (length set1) (length set2) 0) #t]
; Check if 'car of set1` is a list and invoke another cond if true.
[(list? (car set1))
(cond
;Check if car of set2 is a list.
[(list? (car set2))
(cond
;Recursive case: Invoke the function `set-equal?` with the cars of set1 and set2 as parameters. If they equal, call `nested-set-equal? again with the cdrs of set1 and set2 as next parameters.
[(not (false? (set-equal? (car set1) (car set2)))) (nested-set-equal? (cdr set1) (cdr set2))]
;Recursive case: If invoking 'set-equal?' with the cars of set1 and set2 as parameters returns false, move on to the next element in set1 and compare that to the car of set2.
[(false? (set-equal? (car set1) (car set2))) (nested-set-equal? (cdr set1) (car set2))] ;<- I am certain that this line is what I need help with.
)
]
;If the `car of set2` is a number, call the function by removing the car of set2 from set1 and submitting it as its first parameter and submitting the `cdr of set2` as its second parameter.
[(number? (car set2)) (nested-set-equal? (remove (car set2) set1) (cdr set2))]
)
]
;Recursive case: Check if `car of set1` is a number. If it is, move on to next element of set1 and remove matching element from set2.
[(number? (car set1)) (nested-set-equal? (cdr set1) (remove (car set1) set2))]
)
)
(nested-set-equal? '(1 2 (3 4 5)) '(2 (4 3 5) 1)) ;returns #t.
(nested-set-equal? '((5 6) (7 8)) '((8 7) (6 5))) ;should return #t but returns #f instead
Please help me at your earliest convenience.
Try using mutual recursion, as follows (assuming that there are no repeated elements in lists representing sets):
#lang racket
; Checks if two elements x and y are equal (i.e.,
; they represent the same number or the same set).
; > (elem-equal? 1 1)
; #t
; > (elem-equal? '(1 2) '(2 1))
; #t
; > (elem-equal? '(1 2) '(1 3))
; #f
(define (elem-equal? x y)
(or (and (number? x) (number? y) (= x y))
(and (list? x) (list? y) (set-equal? x y))))
; Removes an element x from a set s, and returns the resulting set
; (if x is not in s, returns #f).
; > (set-remove 3 '(1 (1 3) 2 3))
; '(1 (1 3) 2)
; > (set-remove 3 '(1 (1 3) 2))
; #f
; > (set-remove '(3 1) '(1 (1 3) 2))
; '(1 2)
; > (set-remove '(1 4) '(1 (1 3) 2))
; #f
(define (set-remove x s)
(cond [(empty? s) #f]
[(elem-equal? x (first s)) (rest s)]
[else (let [(r (set-remove x (rest s)))]
(if r
(cons (first s) r)
#f))]))
; Checks if two sets are equal.
; > (set-equal? '(1 2 (3 4 5)) '(2 (4 3 5) 1))
; #t
; > (set-equal? '((5 6) (7 8)) '((8 7) (6 5)))
; #t
; > (set-equal? '((5 6) ((9) 7 8)) '((8 (9) 7) (6 5)))
; #t
; > (set-equal? '((5 6) ((9) 7 8)) '((8 (9 4) 7) (6 5)))
; #f
(define (set-equal? s1 s2)
(cond [(empty? s1) (empty? s2)]
[(empty? s2) (empty? s1)]
[else (let [(r (set-remove (first s1) s2))]
(if r
(set-equal? (rest s1) r)
#f))]))