列表中不常见的输出元素

Question

我创建了一个函数，它应该 return 两个列表没有共同点的元素。目前，他们正在输出传递给它的内容。关于如何解决这个问题有什么建议吗？

(define (findDifference lst1 lst2)
    (if (null? lst1) lst2
    (cons (car lst1) (findDifference (cdr lst1) lst2))))

(findDifference '(2 3 4 (2 3) 2 (4 5)) '(2 4 (4 5))

当前输出：(2 3 4 (2 3) 2 (4 5) 2 4 (4 5)) 期望的输出：(3 (2 3))

Answer 1

因为看起来像是作业，又不想破坏乐趣，这里是蛮力算法，省略了一些位。如果你真的卡住了，我会给你完整的源码。

(define (sym-diff xs ys)
  ;; Since we have the helper function we can determine all the elements that are in the first list, 
  ;; but not in the second list.
  ;; Then we can pass this intermediate result to the second call to sym-diff-helper. 
  ;;This will return us all the elements that are in the second list but not the first.
  (let ((in-first-not-second ...))
    (sym-diff-helper ys xs in-first-not-second)))

;; This function will return all the elements from the first list that are not in the second list!
(define (sym-diff-helper xs ys acc)
  (cond
    ;; If the first list is empty we have checked it.
    (...
     acc)
    ;; If the first list is not empty yet, check if the first element 
    ;; is in the second list.
    ;; If so, discard it and continue with the rest of the list.
    ((member ... ...)
     (sym-diff-helper ... ... ...)
    ;; If the first element of the first list is not in the second list, 
    ;; add it to the accumulator and continue with the rest of the list.
    (else
     (sym-diff-helper ... ... ...)))

(sym-diff-helper '(1 2 3) '(2 3 4) '())
;; == (1)
(sym-diff-helper '(1 2 (3 4) 5) '(2 3 4) '())  
;; == (5 (3 4) 1)


(sym-diff '(2 3 4 (2 3) 2 (4 5)) '(2 4 (4 5)))
;; == ((2 3) 3)

请注意，我选择使用 member。还有一些其他搜索功能，但它们不太适合这种情况。因此，我把它留在那里。可以在此处找到有关搜索功能的更多信息：http://docs.racket-lang.org/reference/pairs.html#%28part..List.Searching%29

Answer 2

您要的是两个列表的 symmetric difference。试试这个：

(define (diff list1 list2)
  (union (complement list1 list2)
         (complement list2 list1)))

使用以下帮助程序：

(define (union list1 list2)
  (cond ((null? list1) list2)
        ((member (car list1) list2) (union (cdr list1) list2))
        (else (cons (car list1) (union (cdr list1) list2)))))

(define (complement list1 list2)
  (cond ((null? list1) '())
        ((member (car list1) list2) (complement (cdr list1) list2))
        (else (cons (car list1) (complement (cdr list1) list2)))))

另请注意，如果您使用的是 Racket，则只需使用内置的 set-symmetric-difference 过程即可达到相同的效果。例如：

(diff '(2 3 4 (2 3) 2 (4 5)) '(2 4 (4 5)))
=> '(3 (2 3))

列表中不常见的输出元素

Output Elements in List That Are Not Incommon

scheme