Racket:我如何修复我的代码，使其返回所有丢失的翻转对

Question

此函数应返回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))

如何修复我的代码，使其返回所有丢失的翻转对例如，我的代码只返回L和最后一个丢失的翻转对(ca(，而不是(ba(和(ca(

;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的意思是"；CCD_ 2使用该函数列表，然后CCD_"在Racket中，无论何时and将任何值组合在一起，结果都将是提供给它的最后一个值或false。例如，如果value1和value2都不是false(如果其中一个是false，则结果也是false(，则(and value1 value2)导致value2。由于lambda产生的值从来都不是false，因此andmap的结果将是lambda表达式最后一次调用时的值，在这种情况下，它可能是它在原始列表L中看到的x的最后一个值的列表(cons (list (cadr x)(car x)) L)。这意味着之前所有consed的值根本不计入结果。

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

(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²)。您应该能够更有效地做到这一点，例如通过使用哈希集。