Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Scheme Discussion :

Supprimer doublons dans une liste


Sujet :

Scheme

  1. #1
    Nouveau Candidat au Club
    Supprimer doublons dans une liste
    Bonjour,
    Je souhaite créer une fonction qui supprime les doublons dans une liste.

    par ex: (doublons '(1 1 2 2 4 5)) --> (1 2 4 5)

    Voici mon code:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    (define (doublons l)
      (cond ((or (null? l) (null? (cdr l))) l)
    	((equal? (car l) (cadr l)) (doublons (cdr l)))
    	(else (cons (car l) (doublons (cdr l))))
            )
      )
    Il fonctionne lorsque les éléments de la liste sont des nombres.
    En revanche il ne fonctionne pas pour des éléments autre que des nombres,

    (doublons '((1 1) (1 2) (1 1))) renvoie ((1 1) (1 2) (1 1))

    Comment surmonter ce problème, j'ai passé énormement de temps dessus et reste bloqué.

    Merci d'avance.

  2. #2
    Membre actif
    Bonjour.

    En effet, ça ne marche pas pour les nombres non plus:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    > (doublons '(1 2 1))
    '(1 2 1)
    C'est l'algorithme qui en est coupable.

  3. #3
    Rédacteur/Modérateur

    Bonjour
    Il me semble que le plus simple est de créer une fonction secondaire avec une liste (vide au départ) qui se remplit avec les éléments qui ne sont pas dajà présents dans cette liste.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    (define (doublons l)
        (doublons_helper(l '()))
    doublons_helper renvoyant son second argument lorsque le premier est vide.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  4. #4
    Membre actif
    Ou bien la même récursion terminale sous forme d'un « named let ».

  5. #5
    Rédacteur/Modérateur

    Par exemple.
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  6. #6
    Membre actif
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #lang racket
    (define (remove-duplicates lst)
      (let loop ([curr-lst lst]
                 [acc null])
        (if (null? curr-lst)
            (reverse acc)
            (let ([head (car curr-lst)])
              (loop (cdr curr-lst)
                    (if (member head acc)
                        acc
                        (cons head acc)))))))

    L'idée est la même, c'est seulement la forme qui diffère.

  7. #7
    Rédacteur/Modérateur

    Je n'aime pas beaucoup l'itératif en Scheme, le récursif et plus sympa :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    (define (doublons l)
      (let doublons_helper ([lst l]
                            [rest '()])
        (cond ((null? lst) (reverse rest))
              ((member (car lst) rest) (doublons_helper (cdr lst) rest))
              (else (doublons_helper (cdr lst) (cons (car lst) rest))))))
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  8. #8
    Membre actif
    Citation Envoyé par Trap D Voir le message
    Je n'aime pas beaucoup l'itératif en Scheme, le récursif et plus sympa :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    (define (doublons l)
      (let doublons-helper ([lst l]
                            [rest '()])
        (cond ((null? lst) (reverse rest))
              ((member (car lst) rest) (doublons-helper (cdr lst) rest))
              (else (doublons-helper (cdr lst) (cons (car lst) rest))))))
    Donc c'est le même « named let » que tu as nommé « doublons-helper » alors que je l'ai nommé « loop » (ce terme n'a ici aucune signification spéciale). Avec une vraie fonction auxilière ça serait
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    (define (doublons l)
      (letrec ([doublons-helper (lambda (lst rest)
                                  (cond ((null? lst) (reverse rest))
                                        ((member (car lst) rest) (doublons-helper (cdr lst) rest))
                                        (else (doublons-helper (cdr lst) (cons (car lst) rest)))))])
        (doublons-helper l '())))
    (define (doublons* l)
      (define (doublons-helper lst rest)
        (cond ((null? lst) (reverse rest))
              ((member (car lst) rest) (doublons-helper (cdr lst) rest))
              (else (doublons-helper (cdr lst) (cons (car lst) rest)))))
      (doublons-helper l '()))