recursion - 如何判断 Racket 中两组内容是否相等(不考虑顺序)？

Question

我有一个家庭作业问题，要求我判断两组内容是否相同，无论顺序如何。

例如:(set-equal? (list 1 2 3) (list 3 2 1))是真的

到目前为止，我已经得到了这个代码，

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

这段代码显然不起作用，因为即使两个列表相等，递归也会导致列表 1 和列表 2 的(空)仍然有数据，从而使最终输出为假。

我想我应该这样处理:
根据 list2 中的数据检查 list1 中的数据，如果数据相同，则将其从两个列表中删除。然后继续检查直到两个列表都为空(给出真)或一个为空而一个仍然有数据(输出假)。问题是，我不知道如何编码。

谁能给我一些关于如何解决这个问题的提示？

Answer 1

回想一下集合的数学定义 A是 B 的子集.

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

数学定义可以用 Racket 写成这样:

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

两组相等的定义 A和 B是:

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

Racket 版本是:

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

然而，对于有限集，我们可以做得更好(在速度方面):

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

在 Racket 中:

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