如何修复我的代码以避免在球拍中使用地图时返回重复对？

Question

这个函数应该return L 的传递闭包。例如：

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

这是我在 Racket 中的内容：

(define (Transitive-Closure L)
  (apply append
  ; Iterate over each pair (a b) in L,
  (map (lambda (x)
            ;Iterate over each pair (c d) in L,
            (map (lambda (y)
                      (let ([a (car x)]
                            [b (cadr x)]               
                            [c (car y)]
                            [d (cadr y)])
                        ;if b equal to c, and (a d) does not exist in L, it will add (a d) to L . Otherwise, return L.
                        (if  (and (eq? b c) (not (member (list a d) L)))
                             (list a d)
                             (append x))))L)) L)))

我的代码只有在不可传递时才有效。我如何修改我的代码以避免 return 在传递时出现重复对？

例如，我的输出：

;This is wrong. It should return '((a b)(b c)(a c)) 
(Transitive-Closure '((a b)(b c)(a c))) ---> '((a b) (a b) (a b) (b c) (b c) (b c) (a c) (a c) (a c))
; This is right.
(Transitive-Closure '((a b)(b a)))---> '((a b) (a a) (b b) (b a))

Answer 1

这不是 map 问题，而是 foldr 问题，因为您没有就地修改列表，而是将列表压缩为一个项目。该项目恰好是 list，但重要的是，该列表可以小于地图 return。您还可以根据该对是否已存在于我们的累加器中来检查是否应该在另一个 if 语句中添加。

如果顺序无关紧要（我假设您只想要集合，如果不是这种情况请告诉我）这很有效

(define (Transitive-Closure L)
  ; Iterate over each pair (a b) in L,
  (foldr (lambda (x transitive-pairs)
            ;Iterate over each pair (c d) in L,
            (foldr (lambda (y sofar)
                      (let ([a (car x)]
                            [b (cadr x)]               
                            [c (car y)]
                            [d (cadr y)])
                        ;if b equal to c, and (a d) does not exist in L, it will add (a d) to L . Otherwise, return L.
                        (cond [(and (eq? b c) (not (member (list a d) L))) (cons (list a d) sofar)]
                              [(not (member x sofar)) (cons x sofar)]
                              [else sofar])))
                               transitive-pairs L)) '() L))

(check-expect (Transitive-Closure '((a b) (b c) (a c))) '((a b) (b c) (a c)))
(check-expect (Transitive-Closure '((a a) (b b) (c c))) '((a a) (b b) (c c)))
(check-expect (Transitive-Closure '((a b) (b a))) '((a b) (a a) (b b) (b a)))
(check-expect (Transitive-Closure '((a b) (b a) (a a))) '((a b) (b b) (b a) (a a)))
(check-expect (Transitive-Closure '((a b) (b a) (a a) (b b))) '((a b) (b a) (a a) (b b)))

如何修复我的代码以避免在球拍中使用地图时返回重复对？

How can I fix my code to avoid returning duplicate pairs while using map in racket?

scheme

duplicates

racket

transitive-closure