Блог

Главная - Вопросы по программированию - Как я могу исправить свой код, чтобы избежать возврата повторяющихся пар при использовании map в racket?

Как я могу исправить свой код, чтобы избежать возврата повторяющихся пар при использовании map в racket?

#duplicates #scheme #racket #transitive-closure

#дубликаты #схема #racket #транзитивное закрытие

Вопрос:

Эта функция должна возвращать транзитивное замыкание 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)))

Мой код работает только тогда, когда он не является транзитивным. Как я могу изменить свой код, чтобы избежать возврата повторяющихся пар, когда он транзитивный?

Например, мой вывод:

 ;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))

Комментарии:

1. Ну, вы могли бы использовать remove-duplicates , чтобы избавиться от избыточных элементов…

2. Алгоритм в любом случае неверен — наверняка вам понадобится некоторая рекурсия, а не просто два вызова map. Выясните это, прежде чем беспокоиться о дубликатах. Например, рассмотрим ((a b) (b c) (c d)) . Это должно быть включено (a d) в результат, но ваша функция, как написано, не будет включать его.

3. Вы добавляете x каждый раз, когда условие ложно, что может произойти более одного раза.

Ответ №1:

Это не проблема, это проблема, потому что вы не изменяете список на месте, вы сокращаете список до одного элемента. map foldr Этот элемент оказывается a list , но важно, что список может быть меньше, чем может вернуть map. Также вы можете проверить, следует ли добавлять или нет в другом 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)))