Come eliminare i duplicati in un elenco, ma mantenere l'ordine

Question

Sto usando Studente intermedio con Lambda in DrRacket, mi chiedevo come rimuovere i duplicati in un elenco, mantenendo l'ordine. Ad esempio (remove-dup (list 2 5 4 5 1 2)) produrrebbe (list 2 5 4 1). Finora, ho questo:

(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)))])) 

, ma c'è un problema dal momento che non mantiene l'ordine. Qualcuno può indicarmi la giusta direzione? Grazie per il tuo tempo.

Answer 1

SRFI-1 ha delete-duplicates, anche se è inefficiente. (Io non sono troppo familiare con la racchetta, ma sicuramente ha SRFI-1, e la fonte ...)

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

Answer 2

Run attraverso la lista in modo sequenziale, l'inserimento di ogni elemento in una tabella hash o altro dizionario. Se si tenta di inserire un elemento già presente nella tabella hash, non aggiungerlo all'elenco in uscita.

Answer 3

Se il vostro obiettivo è quello di ottenere il lavoro funzionalità, e non qualche domanda compiti a casa, quindi non c'è bisogno di fare nulla, basta usare remove-duplicates:

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

Answer 4

Quello che dovete fare è confrontare in retromarcia ordina tutto il tempo. È possibile utilizzare la funzione reverse che restituisce un elenco in ordine inverso. In questo modo rimuovi sempre la seconda occorrenza di un elemento e non il primo. Ecco un esempio, tuttavia utilizza let e if e non un'espressione cond.

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

Buona fortuna con i compiti a casa :)

Answer 5

non sono sicuro se questo è compiti a casa, ma nel caso in cui è vi posterò solo l'idea. Se non mi dice e posso mettere una soluzione qui.

Ciò di cui hai bisogno è tenere traccia degli oggetti unici che trovi, puoi farlo usando un elenco ausiliario, come un accumulatore, per tenere traccia di quelli che hai trovato finora.

Ogni volta che si guarda un altro elemento controllare se è nella lista ausiliaria. Nel caso non lo aggiunga alla lista ausiliaria.

Finirai con l'ordine inverso di quello che stai cercando di trovare, quindi puoi solo (invertire ...) e avrai la tua risposta.

Answer 6

hmm Ho appena avuto un esame racchetta di recente,:/

'standard' remove-duplicates funziona bene, ma stavo usando pretty-grande nel DrRacket così doveva essere caricato utilizzando (require racket/list)

qui è un modo alternativo :)

con mutazione (non proprio nello spirito della racchetta ma .. funziona.)

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

speranza questo aiuta ... evviva!

Answer 7

Questa è la soluzione:

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

Answer 8

vecchia questione, ma questo è un'implementazione dell'idea di 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)))]))