Absence de doublons dans une liste☘
Important
On rappelle que l'entraînement à la programmation est indispensable pour apprendre à programmer...
Exercice 1☘
Écrire une fonction python spécifiée comme suit:
def absent_apres(liste, indice):
"""
liste -- une liste d'éléments quelconques
indice -- un indice de la liste (entier entre 0 et len(liste)-1)
renvoie True si liste[indice] est absent de liste[indice+1..]
et renvoie False si liste[indice] est présent dans liste[indice+1..].
>>> absent_apres([2, 42, 7, 8, 42, 9], 1)
False
>>> absent_apres([2, 42, 7, 8, 42, 9], 4)
True
"""
Une réponse
Un code possible:
def absent_apres(liste, indice):
"""
liste -- une liste d'éléments quelconques
indice -- un indice de la liste (entier entre 0 et len(liste)-1)
renvoie True si liste[indice] est absent de liste[indice+1..]
et renvoie False si liste[indice] est présent dans liste[indice+1..].
>>> absent_apres([2, 42, 7, 8, 42, 9], 1)
False
>>> absent_apres([2, 42, 7, 8, 42, 9], 4)
True
"""
element = liste[indice]
apres = [liste[k] for k in range(indice+1, len(liste))]
return not(element in apres)
Autre version
La fonction python précédente peut être écrite ainsi:
def absent_apres_version2(liste, indice):
"""
liste -- une liste d'éléments quelconques
indice -- un indice de la liste (entier entre 0 et len(liste)-1)
renvoie True si liste[indice] est absent de liste[indice+1..]
et renvoie False si liste[indice] est présent dans liste[indice+1..].
>>> absent_apres_version2([2, 42, 7, 8, 42, 9], 1)
False
>>> absent_apres_version2([2, 42, 7, 8, 42, 9], 4)
True
"""
element = liste[indice]
for k in range(indice+1, len(liste)):
if element == liste[k]:
return False
return True
Variante
Un code possible:
def absent_apres(liste, indice):
"""
liste -- une liste d'éléments quelconques
indice -- un indice de la liste (entier entre 0 et len(liste)-1)
renvoie True si liste[indice] est absent de liste[indice+1..]
et renvoie False si liste[indice] est présent dans liste[indice+1..].
>>> absent_apres([2, 42, 7, 8, 42, 9], 1)
False
>>> absent_apres([2, 42, 7, 8, 42, 9], 4)
True
"""
return len([liste[k] for k in range(indice+1, len(liste)) if liste[k] == liste[indice]]) == 0
Exercice 2☘
A l'aide de la fonction de l'exercice précédent, on veut définir une fonction python spécifiée ainsi:
def alldiff(liste):
"""
liste -- liste d'éléments
renvoie True si tous les éléments de liste sont distincts, renvoie False
si deux éléments au moins ont la même valeur.
>>> alldiff([3, 4, 7, 4])
False
>>> alldiff([3, 4, 7, 42])
True
"""
- Décrire un principe (en français ou pseudo-code) de résolution du problème.
Principe
Soit n = len(liste).
- On vérifie que l'élément liste[0] est absent de liste[1..]
- On vérifie que l'élément liste[1] est absent de liste[2..]
- On vérifie que l'élément liste[2] est absent de liste[3..]
- ...
- On vérifie que l'élément liste[n-2] est absent de liste[n-1..]
Pourquoi ne vérifie-t-on que les éléments se trouvant après?
- A l'étape 2, on n'a pas besoin de regarder si liste[1] est égal à liste[0] car cela a déjà été vérifié avec l'étape sur liste[0].
- De même, à l'étape 3, on n'a pas besoin de regarder si liste[2] est égal à liste[0] ou à liste[1] car cela a déjà été vérifié avec les étapes sur liste[0] et liste[1].
- etc
Pseudo-code
Soit n = len(liste).
reponse ← vrai
Pour i allant de 0 à n-2:
si liste[i] est présent dans liste[i+1..]:
reponse ← faux
sinon:
ne rien faire
renvoyer reponse
- Traduire le principe précédent en code Python.
Une réponse
Un code possible:
def absent_apres(liste, indice):
"""
liste -- une liste d'éléments quelconques
indice -- un indice de la liste (entier entre 0 et len(liste)-1)
renvoie True si liste[indice] est absent de liste[indice+1..]
et renvoie False si liste[indice] est présent dans liste[indice+1..].
>>> absent_apres([2, 42, 7, 8, 42, 9], 1)
False
>>> absent_apres([2, 42, 7, 8, 42, 9], 4)
True
"""
element = liste[indice]
apres = [liste[k] for k in range(indice+1, len(liste))]
return not(element in apres)
def alldiff(liste):
"""
liste -- liste d'éléments
renvoie True si tous les éléments de liste sont distincts, renvoie False
si deux éléments au moins ont la même valeur.
>>> alldiff([3, 4, 7, 4])
False
>>> alldiff([3, 4, 7, 42])
True
"""
for i in range(len(liste)-1):
if not(absent_apres(liste, i)):
return False
return True
Exercice 3☘
Dans l'exercice précédent, nous avons répondu à la question en deux fonctions.
Essayez de "compacter" le code en une seule fonction.
Note
Compacter le code n'est pas nécessairement une bonne pratique car le code résultant pourra être moins lisible... A vous de voir dans chaque situation ce qui rend l'ensemble plus lisible, plus maintenable.
L'objectif de cet exercice est ici de vous faire réfléchir à la programmation indépendamment de la lisibilité...
Dans vos scripts, vous devez privilégier systématiquement la lisibilité (et non la compacité) du code.
Principe
Chacune des deux fonctions fait intervenir une boucle. Le principe est donc ici d'imbriquer les boucles plus explicitement dans le code.
Une réponse
def alldiff(liste):
"""
liste -- liste d'éléments
renvoie True si tous les éléments de liste sont distincts, renvoie False
si deux éléments au moins ont la même valeur.
>>> alldiff([3, 4, 7, 4])
False
>>> alldiff([3, 4, 7, 42])
True
"""
for i in range(len(liste)-1):
if liste[i] in [liste[k] for k in range(i+1, len(liste))]:
return False
return True
autre code
Le code précédent est équivalent à celui-ci:
def alldiff(liste):
"""
liste -- liste d'éléments
renvoie True si tous les éléments de liste sont distincts, renvoie False
si deux éléments au moins ont la même valeur.
>>> alldiff([3, 4, 7, 4])
False
>>> alldiff([3, 4, 7, 42])
True
"""
for i in range(len(liste)-1):
for k in range(i+1, len(liste)):
if liste[i] == liste[k]:
return False
return True