递归比较两个集合是否相等？
我对一般编程相当陌生，正在尝试构造一个函数，该函数将两个集合作为输入，其中可以包含其他集合 (a (bc) de (fg (h)), (abc (def)) 例如，并返回，无论它们是否相等，如果有帮助的话，我正在使用计划，但我真的想想象一下我可以如何做到这一点，谢谢您的帮助。
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一种简单的递归方法是选择集合 A 中的一个元素，然后在集合 B 中查找相等的元素。如果找到，则从 A 和 B 中删除这两个元素并递归。如果两组都为空，则成功停止；如果正好有一个为空，或者 A 中选定的元素在 B 中没有对应的元素，则停止并失败。
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.
有些语言有内置的集合类型，包括 Racket。因此，唯一的问题是将列表（可能包含其他列表）转换为嵌套集。所以像这样：（警告 - 完全未经测试的代码）
基本上我们不考虑原子，并使用内置的
list->set函数在递归转换 元素。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)
Basically we leave atoms alone, and build a set out of a list using the builtin
list->setfunction on recursively converted elements.两个关键点：
(a) 各个组件的匹配类型相同性测试
(b) 当到达“核心”元素值时测试匹配值
无论您使用什么编程语言，如果我们查看列表的一部分，例如 (a (bc)...) 和 (abc ... ），在看到“a”后我们会注意到每个都是不同的类型。第一个列表后面是一个列表，而第二个列表后面是另一个非列表元素。语言可能会失败（发出某种错误信号），或者允许您以类似的方式考虑每种不同类型，但通常会提供一种查询类型的方法。
在方案中（我记不太清了），第一个列表的 car 值为 a，其 cdr 值为列表（ (bc) ...）。第二个列表的 car 值为 a，但 cdr 返回列表 (bc ...)。除非语言提供了不同的“相同性”观点，否则这两者不可能相同。
这种对对象类型的测试将是查看列表是否相同的第一步。
接下来，我们测试已验证的相同结构中相应位置的基本元素值。我们必须以正确的方式遍历结构（即依赖于结构细节）。
遍历的算法细节取决于编程语言。有些语言在避免错误和测试相同性方面比其他语言提供更多帮助。
我们可以使用递归或迭代方法。有了方案，从概念上讲，递归就更自然了。
示例伪代码，其中类型和值均由组成的 test =? 处理
我们注意到递归。其作用是，如果您获得一个简单元素，它会测试相等性并返回该值。如果直接调用该函数，则这就是最终答案，如果递归调用该函数，则它将将该答案发送回函数调用链，从而使某些嵌套 (f cdr(l1) cdr(l2)) 返回 false 或 true并最终使最高级别的调用也返回 false 或可能仍然能够返回 true （注意“和”要求及其工作原理。仅当每个部分都为 true 时才会出现 true，而如果任何部分为 false 则发生 false）。类似地，如果该函数获取一个列表，那么它会测试汽车部件，并在列表的其余部分再次递归调用自身时，将其与它得到的任何值“和”。因此，该函数可以处理您提供的任何复杂的子列表结构中的列表和非列表。 [记住，我们假设=？管理类型和值检查，例如， (=? b '(b)) 将是 #f]
[另外，请参阅 http://cs.gettysburg.edu/~tneller/cs341/scheme-intro/exercises.html#Equivalence 了解您可能会用到的内容测试等价性。]
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 =?
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.]