Làm thế nào để loại bỏ các bản sao trong danh sách, nhưng giữ thứ tự

Question

Tôi đang sử dụng Sinh viên trung cấp với Lambda trong DrRacket, tôi đã tự hỏi làm thế nào để loại bỏ các bản sao trong danh sách, trong khi vẫn giữ thứ tự. Ví dụ: (remove-dup (list 2 5 4 5 1 2)) sẽ sản xuất (list 2 5 4 1). Cho đến nay, tôi có điều này:

(define (remove-duplicates lst) 
    (cond 
    [(empty? lst) empty] 
    [(member? (first lst) (rest lst)) 
    (remove-duplicates (rest lst))] 
    [else (cons (first lst) (remove-duplicates (rest lst)))])) 

, nhưng có vấn đề vì nó không giữ được thứ tự. Ai đó có thể chỉ cho tôi đi đúng hướng? Cảm ơn vì đã dành thời gian cho tôi.

Answer 1

SRFI-1 có delete-duplicates, mặc dù không hiệu quả. (Tôi không quá quen thuộc với vợt, nhưng chắc chắn nó có SRFI-1, và các nguồn ...)

http://srfi.schemers.org/srfi-1/srfi-1.html#delete-duplicates

Answer 2

Chạy qua danh sách tuần tự, chèn mỗi phần tử trong một bảng băm hoặc bộ từ điển khác. Nếu bạn cố chèn một phần tử đã có trong bảng băm, đừng thêm nó vào danh sách gửi đi.

Answer 3

Nếu mục tiêu của bạn là để có được chức năng làm việc, chứ không phải một số câu hỏi bài tập về nhà, sau đó bạn không cần phải làm bất cứ điều gì, chỉ cần sử dụng remove-duplicates:

Welcome to Racket v5.2. 
-> (remove-duplicates (list 2 5 4 5 1 2)) 
'(2 5 4 1) 

Answer 4

Những gì bạn cần làm là so sánh ngược lại đặt hàng toàn bộ thời gian. Bạn có thể sử dụng hàm reverse trả về một danh sách theo thứ tự ngược lại. Bằng cách đó, bạn luôn xóa 2 lần xuất hiện của một phần tử chứ không phải phần tử đầu tiên. Dưới đây là một ví dụ, tuy nhiên nó đang sử dụng let và if và không phải là biểu thức cond.

http://www.cs.bgu.ac.il/~elhadad/scheme/duplicates.html

Chúc may mắn với bài tập về nhà của bạn :)

Answer 5

Tôi không chắc chắn nếu điều này là bài tập ở nhà, nhưng trong trường hợp nó là tôi sẽ đăng chỉ là ý tưởng. Nếu nó không nói với tôi và tôi có thể đặt một giải pháp ở đây.

Điều bạn cần là theo dõi các mục duy nhất bạn tìm thấy, bạn có thể thực hiện điều đó bằng cách sử dụng danh sách phụ, như bộ tích lũy để theo dõi những mục bạn đã tìm thấy từ trước tới nay.

Bất cứ khi nào bạn nhìn vào một mục khác, hãy kiểm tra xem nó có nằm trong danh sách phụ trợ hay không. Trong trường hợp nó không thêm nó vào danh sách phụ trợ.

Bạn sẽ kết thúc với thứ tự ngược lại những gì bạn đang cố gắng tìm, vì vậy bạn chỉ có thể (đảo ngược ...) và bạn sẽ có câu trả lời.

Answer 6

hmm tôi chỉ có một bài kiểm tra vợt gần đây,:/

các 'tiêu chuẩn' remove-duplicates hoạt động tốt nhưng tôi đã sử dụng khá-lớn trong drRacket vì vậy nó phải được nạp bằng (require racket/list)

đây là một cách khác :)

sử dụng đột biến (không thực sự theo tinh thần vợt nhưng .. nó hoạt động.)

(define (set l) 
     (define the-set '()) 
      (begin (for-each 
         (lambda (x) 
          (if (member x the-set) 
           #t 
          (set! the-set (cons x the-set)))) 
         l) 
        (reverse the-set))) 

niềm hy vọng này giúp ... chúc mừng!

Answer 7

Đây là giải pháp:

(define (remove-duplicates lon) 
    (foldr (lambda (x y) (cons x (filter (lambda (z) (not (= x z))) y))) empty lon)) 

Answer 8

Cũ câu hỏi, nhưng điều này là một thực hiện ý tưởng J-Y.

(define (dup-rem lst) 
    (cond 
    [(empty? lst) empty] 
    [else (cons (first lst) (dup-rem (filter (lambda (x) (not (equal? (first lst) x))) lst)))]))