list - 删除重复项并对列表进行排序

Question

我正在尝试编写一个过程，该过程接受一个可能包含或不包含重复项的列表，然后返回该列表而不包含重复项，并按排序顺序排列。到目前为止我想到的是:

(define (remove-duplicated list)
    (if (null? list)
       '()
        (if (= (car list) (cadr list))
            (cdr list)
            (cons (car list) (remove-duplicates (cdr list))))))  

除了对列表进行排序之外，我不太确定问题出在哪里。例如，如果我输入

(remove-duplicates '(3 3 4 5 6 6 7))

返回

(3 4 5 6 6 7)

Answer 1

a fairly simple procedure that will take in a list that may or may not include duplicats, and then return that list without any duplicates included, and in sorted order.

至少有两种方法可以做到这一点:

• 删除重复项后对列表进行排序；或
• 列表排序后删除重复项。

Óscar López pointed out那个

[Your] implementation fails because you're only testing for two consecutive values, you have to search the current element in the rest of the list, use member for that.

如果您在 排序之前删除重复项，这将是一个问题，因为列表中的给定元素可能在列表中的其他任何位置都有重复项。但是，如果您首先对列表进行排序，那么可以保证任何重复的元素做 紧跟在原始元素之后，因此您不需要检查整个列表。如果列表已排序，则删除重复项会更容易，但在删除重复元素后，对列表进行排序实际上并不容易，因此首先对列表进行排序然后然后删除重复项确实有意义。 (我想你可以更有效率，并编写你自己的 sort-and-remove-duplicates 过程，但几乎可以肯定不是真的有必要。)

如果您假设 list 已经排序，您的代码几乎是正确的。有两个必要的调整:

1. 在基本情况下，您只检查是否 (null?list)。但是，对于非空列表，您随后比较 (car list) 和 (cadr list)，但如果 list 只有一个元素, 那么 (cadr list) 是一个错误。幸运的是，只有一个元素的列表没有重复项，因此您的基本情况可以是 (or (null? list) (null? (cdr list)))。
2. 第二个 if 的 then 部分需要是 (remove-duplicated (cdr list))，而不是 (cdr list)，因为 list 仍然可以有更多重复项(例如，(x x x ...) 或 (x x y y ...)).

这是经过修改和一些注释后的代码:

(define (remove-duplicated list)
  ;; remove duplicates from a *sorted* list.  Because the 
  ;; list is sorted, any duplicates of an element will
  ;; immediately follow the first occurrence of the element.
  ;;---------------------------------------------------------
  ;; If the list has the form () or (x)
  (if (or (null? list)
          (null? (cdr list)))
      ;; then it has no duplicates, so return it
      list
      ;; otherwise, if the list looks like (x x ...)
      (if (= (car list) (cadr list))
          ;; then you can discard the first element, but you
          ;; still need to remove duplicates from the rest of
          ;; the list, since there can be more duplicates later
          (remove-duplicated (cdr list))
          ;; otherwise, you need the first element of the list
          ;; and can simply remove-duplicated from the rest.
          (cons (car list) (remove-duplicated (cdr list))))))  

这按预期工作:

(remove-duplicated '(1 1 2 3 3 4 5 6))
;=> '(1 2 3 4 5 6)