Discussion :

[yrmab]

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.

[byjav]

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.

[Trap D]

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.

[byjav]

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

[Trap D]

Par exemple.

[byjav]

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.

[Trap D]

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

[byjav]

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
11
12
13
(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 '()))