Aller au contenu

Trier des chaînes de caractères☘

On peut comparer des nombres mais aussi des chaînes de caractère:

>>> 'a'<'b'
True
>>> 'aa' < 'ab'
True
>>> 'aa' < 'a'
False

La comparaison est celle qui permet d'ordonner les mots dans le dictionnaire.

Tri du dictionnaire☘

Trier la liste 

L = ['python', 'java', 'javascript', 'go', 'ruby', 'prolog', 'scheme', 'ocaml']
  • suivant l'ordre du dictionnaire,
  • suivant l'ordre inverse du dictionnaire.
Solution
  • L'ordre du dictionnaire:
>>> L = ['python', 'java', 'javascript', 'go', 'ruby', 'prolog', 'scheme', 'ocaml']
>>> L.sort()
>>> L
['go', 'java', 'javascript', 'ocaml', 'prolog', 'python', 'ruby', 'scheme']
  • L'ordre inverse du dictionnaire:
>>> L = ['python', 'java', 'javascript', 'go', 'ruby', 'prolog', 'scheme', 'ocaml']
>>> L.sort(reverse=True)
>>> L
['scheme', 'ruby', 'python', 'prolog', 'ocaml', 'javascript', 'java', 'go']

Tri suivant le nombre de 'e'☘

Trier des listes de mots suivant le nombre croissant de 'e' contenus dans chaque mot.

Nombre de 'e'

On commence par définir une fonction prenant en paramètre une chaîne et renvoyant le nombre de lettres "e" contenues dans la chaîne.

def nombre_e(mot):
    """
    mot est une chaîne de caractères
    renvoie le nombre de caractères 'e' contenus dans mot.
    """
    compteur = 0
    for caractere in mot:
        if caractere == 'e':
            compteur += 1
    return compteur

Une variante:

def nombre_e(mot):
    """
    mot est une chaîne de caractères
    renvoie le nombre de caractères 'e' contenus dans mot.
    """
    return len([c for c in mot if c == 'e'])
le tri
  • Avec sort:
def tri_suivant_nb_e(tab):
    """
    tab: liste de chaînes de caractères
    trie tab  suivant le nombre de 'e' des éléments 
    """
    tab.sort(key=nombre_e)

Exemple d'utilisation:

>>> T = ['elephant', 'the', 'tea', 'barrique', 'etete']
>>> tri_suivant_nb_e(T)
>>> T
['the', 'tea', 'barrique', 'elephant', 'etete']
  • Avec sorted :
def tri_suivant_nb_e(tab):
    """
    tab: liste de chaînes de caractères
    renvoie une liste, de mêmes éléments que tab, triée  suivant le nombre de 'e' des éléments 
    """
    return sorted(tab, key=nombre_e)

Exemple d'utilisation:

>>> T = ['elephant', 'the', 'tea', 'barrique', 'etete']
>>> tri_suivant_nb_e(T)
['the', 'tea', 'barrique', 'elephant', 'etete']

Critère double☘

On reprend le critère précédent: trier les chaînes d'une liste suivant le nombre croissant de 'e'.
Mais on aimerait de plus que lorsque deux chaînes présentent le même nombre de 'e', alors la plus longue des deux chaînes soit placée après la plus courte.

Comment procéder ?

le principe

L'idée est de faire deux tris successifs:

  • l'un suivant la longueur,
  • le second suivant le nombre de 'e'.

Attention, il faut bien respecter l'ordre indiqué: d'abord le tri suivant la longueur puis le tri suivant le nombre de 'e'.

Exemple.

On aimerait trier la liste L = ['eee', 'abba', 'bac', 'le', 'elephant', 'feter', 'tete'].

  • Un tri (avec sort) suivant la longueur
    donne L = ['le', 'eee', 'bac', 'abba', 'tete', 'feter', 'elephant'].
  • Suivi d'un tri suivant le nombre de 'e': L = ['bac', 'abba', 'le', 'tete', 'feter', 'elephant', 'eee']. Le principe de stabilité du tri fait que les éléments ayant le même nombre de 'e' restent triés dans l'ordre croissant de leur longueur obtenu par le tri précédent.

Alors qu'en inversant les tris, on aurait pour cette même liste L = ['eee', 'abba', 'bac', 'le', 'elephant', 'feter', 'tete'] :

  • tri suivant le nombre de 'e': L = ['abba', 'bac', 'le', 'elephant', 'feter', 'tete', 'eee']
  • suivi du tri suivant la longueur: L = ['le', 'bac', 'eee', 'abba', 'tete', 'feter', 'elephant']. Le résultat ne convient pas: le mot 'le' avec un 'e' se retrouve devant les mots 'bac' et 'abba' qui en contiennent zéro. De même 'eee' est placé avant des mots contenant moins de 3 'e'.
Un code avec sort
def nb_e(mot):
    """
    mot est une chaîne de caractères
    renvoie le nombre de caractères 'e' contenus dans mot.
    """
    return len([c for c in mot if c == 'e'])



def tri(tab):
    """
    tab: liste de chaînes de caractères
    trie tab suivant le double critère défini dans l'énoncé
    """
    tab.sort(key=len)
    tab.sort(key=nb_e)

Utilisation:

>>> L = ['eee', 'abba', 'bac', 'le', 'elephant', 'feter', 'tete']
>>> tri(L)
>>> L
['bac', 'abba', 'le', 'tete', 'feter', 'elephant', 'eee']
Un code avec sorted
def tri(tab):
    """
    tab: liste de chaînes de caractères
    renvoie une liste, de mêmes éléments que tab, triée suivant le double critère défini dans l'énoncé.
    """
    t = sorted(tab, key=len)
    return sorted(t, key=nb_e)

Utilisation:

>>> L = ['eee', 'abba', 'bac', 'le', 'elephant', 'feter', 'tete']
>>> tri(L)
['bac', 'abba', 'le', 'tete', 'feter', 'elephant', 'eee']

Remarque.

On peut écrire les deux tris en "enchaînant":

def tri(tab):
    """
    tab: liste de chaînes de caractères
    renvoie une liste, de mêmes éléments que tab, triée suivant le double critère défini dans l'énoncé.
    """
    return sorted(sorted(tab, key=len), key=nb_e)

Tri suvant la présence d'un 'e'☘

On dispose d'une liste de mots. On veut placer en début de liste les mots contenant au moins une lettre 'e'. Proposer une solution basée sur la méthode sort.

Solution

On écrit une fonction prenant en paramètre une chaîne renvoyant une valeur (par exemple 0) si le mot contient 'e', et renvoyant une autre valeur, plus grande que la précédente, si le mot ne contient pas 'e'.

  • Un code possible:
def contient_e(mot):
    """
    mot est une chaîne de caractères
    renvoie 0 si mot contient 'e', renvoie 1 sinon.
    """
    if 'e' in mot:
        return 0
    else:
        return 1
  • En Python, on peut comparer Falseet True:
>>> False < True
True

Ainsi False est une valeur strictement inférieure à la valeur True et notre fonction key pour le tri pourrait être:

def contient_e(mot):
    """
    mot est une chaîne de caractères
    renvoie 0 si mot contient 'e', renvoie 1 sinon.
    """
    return not('e' in mot)
le tri
def tri_suivant_presence_e(tab):
    """
    tab: liste de chaînes de caractères
    trie tab  en plaçant au début les chaînes contenant ''e'
    """
    tab.sort(key=contient_e)

Exemple d'utilisation:

>>> T = ['elephant', 'chat',  'the', 'tea', 'cactus', 'barrique',  'python', 'etete']
>>> tri_suivant_presence_e(T)
>>> T
['elephant', 'the', 'tea', 'barrique', 'etete', 'chat', 'cactus', 'python']