球拍：如何修复我的代码，以便它 return 所有丢失的翻转对？

Question

这个函数应该return L 的对称闭包。示例：

(Symmetric-Closure'((a a) (a b) (b a) (b c) (c b))) ---> '((a a) (a b) (b a) (b c) (c b))
(Symmetric-Closure'((a a) (a b) (a c))) ---> '((a a) (a b) (a c) (b a)(c a))
(Symmetric-Closure'((a a) (b b))) ---> '((a a) (b b))
(Symmetric-Closure'())---> '()

这是我在 Racket 中的内容

(define (Symmetric-Closure L)
  ;Iterate over each pair in L
  (andmap (lambda (x)
             ;If the flipped pair does not exist in L, it will
             ;return L and the flipped pair that is missing. Otherwise, return L.
             (if(not(member (list (cadr x)(car x)) L))
                (cons (list (cadr x)(car x)) L)
                (append L)))
           L))

我如何修复我的代码，以便它 return 所有丢失的翻转对例如，我的代码只有 return L 和最后一个缺失的翻转对 (c a) 而不是 (b a) 和 (c a)

;this is wrong, it should return '((c a)(b a)(a a)(a b)(a c))
(Symmetric-Closure '((a a)(a b)(a c))-----> '((c a)(a a)(a b)(a c)) 
;this is correct
(Symmetric-Closure '((a a)(a b)(b a)(b c)(c b)))-----> '((a a)(a b)(b a)(b c)(c b))

Answer 1

andmap 表示“map 使用此函数的列表，然后 and 一起得到结果。”在 Racket 中，无论何时你 and 任何值，结果要么是最后提供给它的值，要么是 false。例如，如果 value1 和 value2 都不是 false（如果其中之一是 false，则结果是 value2 false）。由于 lambda 产生的值永远不会是 false，因此 andmap 的结果将是最后一次调用 lambda 表达式的值，在本例中，可能是它在原始列表 L 中看到的 x 的最后一个值的列表 (cons (list (cadr x)(car x)) L)。这意味着 consed 的所有前面的值根本不会影响结果。

您可以将其修改为使用简单的 map。但这会产生一个成对列表，而不是你想要的成对列表。所以最后你需要把它压平才能得到结果。

(define (symmetric-closure L)
  ;Iterate over each pair in L
  (apply append
         (map (lambda (x)
                ;If the flipped pair does not exist in L, it will
                ;return L and the flipped pair that is missing. Otherwise, return L.
                (if (not (member (list (cadr x) (car x)) L))
                    (list (list (cadr x) (car x)) x)
                    (list x)))
              L)))

不过，需要注意的一件事是，此算法会为原始列表中的每个元素调用 member。检查列表中的成员资格是 O(N) 并且您正在执行此 N 次，这意味着该算法的复杂性是 O(N²)。您应该能够更有效地执行此操作，例如使用 hash set.

球拍：如何修复我的代码，以便它 return 所有丢失的翻转对？

Racket: How can I fix my code so that it will return all the flipped pairs that is missing?

closures

symmetric

racket