删除重复项并对列表进行排序 [英] Remove duplicates and sort a list

问题描述

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

I am trying to write a procedure that takes a list that may or may not include duplicates, and then return that list without duplicates, and in sorted order. What I came up with so far is:

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

除了对列表进行排序外，我不太清楚问题出在哪里.例如，如果我输入

I'm not quite sure what the problem is, besides sorting the list. For example, if I input

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

返回

(3 4 5 6 6 7)

推荐答案

输入列表可能是已排序的事实使我无所适从.我要描述的内容将适用于从任何列表中删除重复的元素(已排序或未排序).对于删除列表中重复项的一般情况，您必须使用

The fact that the input list might be sorted slipped my mind. What I'm about to describe will work for removing duplicate elements from any list, sorted or not. For the general case of removing duplicates in a list, you have to search the current element in the rest of the list, using member for that.

此外，在这两种情况下，您都必须进行递归，并要注意，在最后一行中，您正在调用

Also, you have to advance the recursion in both cases, and be aware that in the last line you're calling remove-duplicates (which is a built-in procedure in some interpreters, so maybe you don't have to implement it from scratch!), but you named the procedure remove-duplicated. As a side note, it's a bad idea to name a parameter list, that'll clash with a built-in function - I took the liberty of renaming it. This will fix the problems, and it's a more general solution:

; if the input list is not sorted, use this
(define (remove-duplicated lst)
  (if (null? lst)
      '()
      (if (member (car lst) (cdr lst))  ; changes here
          (remove-duplicated (cdr lst)) ; and here
          (cons (car lst)
                (remove-duplicated (cdr lst)))))) 

现在，如果输入列表是按 sorted 开头的，那么这就是解决代码的方法.我的大部分评论都适用，除了您不必使用member并且基本情况有所不同:

Now, if the input list is sorted to begin with, this is how to fix your code. Most of my comments apply, except that you don't have to use member and the base case is a little different:

; if the input list is sorted, use this
(define (remove-duplicated lst)
  (if (or (null? lst) (null? (cdr lst))) ; changes here
      lst
      (if (= (car lst) (cadr lst))
          (remove-duplicated (cdr lst))  ; and here
          (cons (car lst)
                (remove-duplicated (cdr lst))))))

无论哪种方式，只要您将正确的输入用作输入，该过程就会按预期工作(第一个实现用于已排序的或未排序的输入列表，第二个实现仅适用于已排序的列表) ):

Either way, the procedure will work as expected as long as you use the right one for the input (the first implementation is for sorted or unsorted input lists, the second one works only for sorted lists):

(remove-duplicated '(3 3 4 5 6 6 7)) ; sorted input, both implementations work
=> '(3 4 5 6 7)

最后，如果您需要确保输出列表将始终被排序，但不能保证输入列表已被排序，请使用我的第一个实现remove-duplicated并随后对其进行排序，请检查您的解释器以查找哪些排序程序可用-以下将在Racket中工作:

Finally, if you need to make sure that the output list will always be sorted, but have no guarantees that the input list was sorted, then use my first implementation of remove-duplicated and sort it afterwards, check your interpreter to find out which sorting procedures are available - the following will work in Racket:

(sort (remove-duplicated '(3 6 3 7 4 5 6)) <) ; using my first remove-duplicated
=> '(3 4 5 6 7)

...或先对列表进行排序，然后使用我的第二个实现remove-duplicated.您有很多选择可以解决此问题！

… Or sort the list first and then use my second implementation of remove-duplicated. You have so many options to solve this problem!

(remove-duplicated (sort '(3 6 3 7 4 5 6) <)) ; using my second remove-duplicated
=> '(3 4 5 6 7)

这篇关于删除重复项并对列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！