Comparing two sets for equality recursively?

I am pretty new to programming in general and am trying to construct a function that will take as input two sets, which can contain other sets (a (b c) d e (f g (h)), 开发者_开发知识库(a b c (d e f)) for example, and returns whether or not they are equal. I am working with scheme if that helps, but am really trying to just visualize how I could do it. Thanks for the help in advance

---

A simple recursive approach is to pick an element of set A and look for an equal element in set B. If one is found, then remove the two elements from A and B and recurse. Stop with success if both sets are empty; stop with failure if exactly one is empty or if the selected element from A does not have a corresponding element in B.

---

Some languages have built-in set types, including Racket. So the only issue is to convert a list (which may contain other lists) into nested sets. So something like this: (warning - completely untested code)

(require racket/set)
(define (recursive-make-set obj)
  (cond
    [(list? obj) (list->set (map recursive-make-set obj))]
    [else obj]))

Basically we leave atoms alone, and build a set out of a list using the builtin list->set function on recursively converted elements.

---

Two key points: (a) test for matching type sameness of individual components (b) test for matching values when you get to the "core" element values

Whatever programming language you use, if we look at a piece of the lists, eg, (a (b c)...) and (a b c ...), we'll note after we see "a" that each is of a different type. The first list follows "a" with a list while the second list follows a with another nonlist element. Languages will likely fail (signal an error of some sort) or else allow you to consider each of these different types similarly but usually provide a way to query the type.

In scheme (and I don't remember exactly), the first list has its car value be a and its cdr value be the list ( (b c) ...). The second list has a car value of a but the cdr returns the list (b c ...). These two cannot be the same unless the language offers a different view of "sameness".

This sort of testing for object type would be the first step to seeing if the lists are the same.

Next, we test the basic element values in corresponding locations within the already verified identical structures. We must traverse the structures the proper way (ie, dependent on the structure details).

The algorithm details of traversing depend on the programming language. Some languages provide more help than others in avoiding mistakes and in testing for sameness.

We can use recursive or iterative approaches. With scheme, and conceptually, recursive is the more natural.

Sample pseudo-code where both type and value are handled by the made up test =?

function f (l1, l2):
(=? car(l1) car(l2))
and
(f cdr(l1) cdr(l2))

We note the recursion. What this does is that, if you get a simple element, it tests for eqality and returns that value. If that function was called directly, then that is the final answer, if it was called recursively, then it sends that answer back up the chain of function calls making some nested (f cdr(l1) cdr(l2)) return false or true and ultimately making the highest level call also return false or potentially still being able to return true (note the "and" requirement and how it works.. true comes only if every part is true, while false happens if any part is false). Similarly, if the function gets a list, then it tests the car part and "and"s this t/f value with whatever it gets when it calls itself again recursively on the rest of the list. Hence, this function handles both lists and nonlists in whatever intricate structure of sublists you feed it. [remember, we assumed that =? managed both the type and value checks, eg, so that (=? b '(b)) would be #f]

[Also, see http://cs.gettysburg.edu/~tneller/cs341/scheme-intro/exercises.html#Equivalence for what you might use to test equivalence.]