Algorithmique : les listes

Eric Obermeyer - Actualisation: septembre 2014

 

Les listes sont indispensables pour résoudre la plupart des problèmes.

 

I) Généralités. 2

1) Définition. 2

2) Notation. 2

3) ATTENTION, on numérote à partir de zéro. 2

4) Nombre d'éléments d'une liste. 2

5) Parcourir une liste. 2

II) Travailler avec les listes en Python. 2

1) Définir une liste. 2

2) Utiliser range() pour créer une liste régulière d'entiers. 3

3) Créer une copie d'une liste simple ou d'un tableau:  ATTENTION.. 3

4) Concaténer (mettre bout à bout) des listes. 3

5) Ajouter, enlever un élément à une liste. 3

6) Extraction d'une partie "régulière" d'une liste. 4

7) Supprimer une partie d'une liste. 4

8) Tri par ordre croissant d'une liste. 4

9) Autres méthodes. 4

10) Transformer une liste. 5

11) Extraire une  sous-liste d'une liste. 5

12) Tri avancé d'une liste. 5

13) Autres fonctions disponibles: minimum, maximum, somme. 5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I) Généralités

1) Définition

En algorithmique, une liste s de n éléments (n est alors la longueur de la liste)  est une variable constituée de n variables indépendantes appelées termes ou éléments de la liste.

L’équivalent mathématique d'une liste est une suite finie ou encore un n-uplet.

2) Notation

Le contenu d'une liste est noté entre des crochets. Le kième terme (en partant de 0) d'une liste s est noté s[k]

# Pseudo-code ou Python

 

s = [1, 3, 5] définit une liste s de longueur 3. On aura s[0] = 1 et s[2] = 5

Si on effectue les affectations s[2] = s[0] puis s[1] = s[1] + s[2] alors

s = [1, 4, 1]

3) ATTENTION, on numérote à partir de zéro

T[i] est le (i+1)ième élément de liste T, car on numérote les éléments à partir de 0.

4) Nombre d'éléments d'une liste

#  Pseudo-code ou Python

 

len(s) est le nombre d'éléments d'une liste s

par exemple len([1,2,3,5]) = 4

5) Parcourir une liste

On doit souvent "parcourir" l'ensemble des éléments d'une liste pour diverses raisons.

# Python ou Pseudo-code

 

n = len(liste)

for i in range(n):                    # ou pour i variant de 0 à n - 1:

   faire quelque chose avec liste[i]

Ou mieux, car Python offre la possibilité de parcourir tout objet itérable s (c’est le cas d’une liste) de façon plus claire:

# Python

for elem in s:

   faire quelque chose avec elem

 

Python permet  également de parcourir une liste en ayant accès à l'indice et à la valeur de l'élément:

# Python

for ind, elem in enumerate(liste):

   faire quelque chose

II) Travailler avec les listes en Python

1) Définir une liste

s = [1, 4, 9, 16]               définit la liste s = [1, 4, 9, 16]

s = [0]*4                       définit la liste s = [0, 0, 0, 0]

s = [[0]*2 for i in range(3)]   définit la liste s = [[0, 0], [0, 0], [0, 0]]

s = list(range(5))              définit la liste s = [0, 1, 2, 3, 4]

s = [i*i for i in range(5)]     définit la liste s = [0, 1, 4, 9, 16]

s = [f(e) for e in T]           est la liste des f(e) avec e dans T 

 

2) Utiliser range() pour créer une liste régulière d'entiers

a, b, n, p sont des entiers positifs ou négatifs

list(range(n))             est la liste [0, 1, 2,…, n-1]

list(range(a, b))          est la liste [a, a+1, a+2,…, b-1]    

list(range(a, b, p))       est la liste [a, a+p, a+2p,…, b exclu]

Par exemple:

list(range(5)) = [0, 1, 2, 3, 4]

list(range(-2)) = []

list(range(3,5)) = [3, 4]

list(range(-2,3)) = [-2, -1, 0, 1, 2]

list(range(1,10,3)) = [1, 4, 7]

list(range(5,1,-1)) = [5, 4, 3, 2]

list(range(10,-10,-5)) = [10, 5, 0, -5]

3) Créer une copie d'une liste simple ou d'un tableau:  ATTENTION

Si s est une liste, l'instruction t = s ne crée pas une liste t indépendante de s, mais seulement un alias. Par exemple:

s = [1, 2, 3]

t = s

s[1] = 5

print(s, t)           On aura s = t = [1, 5, 2], t a changé aussi…

Pour créer une copie t indépendante d'une liste s, il faut écrire t = list(s) ou t = s.copy() . Par exemple:

s = [1, 2, 3]

t = list(s)     # ou t = s.copy()

s[1] = 5

print(s, t)           On aura s = [1, 5, 2] et toujours t = [1, 2, 3]

Pour créer une copie indépendante d'un tableau, il faut utiliser deepcopy(), fonction du module copy.

Par exemple:

import copy

m = [[1,2],[3,4]]

s = copy.deepcopy(m) est une copie indépendante de s

4) Concaténer (mettre bout à bout) des listes

[1, 2, 3] + [4, 5, 6]      est la liste [1, 2, 3, 4, 5, 6]

[1, 2, 3]*3                est la liste [1, 2, 3, 1, 2, 3, 1, 2, 3]

liste1.append(liste2)      revient à faire liste1 = liste1 + liste2

5) Ajouter, enlever un élément à une liste

liste.append(x)    ajoute x à la fin de liste

liste.insert(i, x) ajoute x en position i de la liste

 

liste.pop()  supprime le dernier élément de liste (et le renvoie)

liste.pop(i) supprime l'élément en position i de liste (et le renvoie)

Par exemple:

s = [1, 2, 3]

s.append(5)           alors s = [1, 2, 3, 5]

s.insert(1, 8)        alors s = [1, 8, 2, 3, 5]

s.pop()               alors s = [1, 8, 2, 3]

a = s.pop(0)          alors s = [8, 2, 3] et a = 1

 

 

6) Extraction d'une partie "régulière" d'une liste

Si s est une liste de n éléments, alors:

s[a:b]     est la liste [s[a], s[a+1],…, s[b-1]]

 

s[a:]      est la liste [s[a], s[a+1],…, s[n - 1]]

s[-a:]     est la liste [s[n - a], s[n – a + 1],…, s[n - 1]]

s[:a]      est la liste [s[0], s[1],…, s[a - 1]]

s[:-a]     est la liste [s[0], s[1],…, s[n - a]]

 

s[::p]     est la liste [s[0], s[p], s[2p], …]

s[a::p]    est la liste [s[a], s[a + p], s[a + 2p], …]

s[:b:p]    est la liste [s[0], s[p], …, s[k.p]]  (avec k.p <b)

s[a:b:p]   est la liste [s[a], s[a + p], s[a + 2p]…, s[a + k.p]] (a+k.p < b)

 

Par exemple:

s = [1, 2, 3, 4, 5]

s[1:]  ou s[-4:]      est la liste  [2, 3, 4, 5]

s[:-1] ou s[:4]       est la liste [1, 2, 3, 4]

s[::2]                est la liste [1, 3, 5]

7) Supprimer une partie d'une liste

del s[i]     supprime de s l'élément s[i]

del s[a:b]   supprime de s les éléments s[a], s[a+1],…, s[b-1]

etc… avec toutes les possibilités du 5)

Par exemple:

s = [1, 2, 3, 4, 5, 6, 7, 8]

del s[1]                   alors s = [1, 3, 4, 5, 6, 7, 8]

del s[3:5]                 alors s = [1, 3, 4, 7, 8] 

del s[1::2]                alors s = [1, 4, 8]

8) Tri par ordre croissant d'une liste

s.reverse() inverse l'ordre des éléments de la liste s

s.sort() trie la liste s par ordre croissant

 

reversed(s) est la liste s à l'envers (mais s n'est pas modifiée)

sorted(s) est la liste s triée (mais s n'est pas modifiée)

Par exemple:

s = [1, 3, 2]

s.reverse()           alors s = [2, 3, 1]

s.sort()              alors s = [1, 2, 3]

9) Autres méthodes

liste.count(x) est le nombre de fois qu'apparait x dans liste

liste.index(x) est l'indice du premier élément de liste qui est égal à x

liste.remove(x) supprime de liste la première occurrence de x

Par exemple:

s = [2, 1, 3, 1, 4]

s.count(1)            renvoie 2

s.index(1)            renvoie 1

s.remove(1)           alors s = [2, 3, 1, 4]

10) Transformer une liste

Pour appliquer une fonction f aux éléments d'une liste et récupérer la liste  t = [ f(s[0]), f(s[1]),…] :

t = [f(elem) for elem in liste]

Par exemple:

def f(x):

   return x*3

s = [1, 2, 3]

t = [f(e) for e in s]           renvoie t = [1, 8, 27]

11) Extraire une  sous-liste d'une liste

Pour extraire  (et éventuellement transformer) dans une liste la sous-liste des éléments x vérifiant une propriété P (ce qui se traduit par p(x) = True)

   [e for e in s if critere(e)] est la liste des éléments de s qui vérifient le critère

   [transfo(e) for e in s if critere(e)] est la liste des transformés des éléments de s qui vérifient le critère

Par exemple:

s = [1, 2 ,3, 4]

[e for e in s if (e % 2) == 1] est la liste [1,3]

 

def multiple_de_3(n):

   return (n % 3) == 0

 

s = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

t = [i for i in s if multiple_de_3(i)]     renvoie t = [3, 6, 9]

t = [i**2 for i in s if multiple_de_3(i)]  renvoie t = [9, 36, 81]

12) Tri avancé d'une liste

# Ces méthodes modifient la liste s

s.sort(key = f) trie la liste s par ordre croissant suivant la fonction f

s.sort(key = f, reverse = True) trie la liste s par ordre décroissant suivant la fonction f

 

# Ces méthodes ne modifient pas la liste s

sorted(s, key = f) est la liste s triée par ordre croissant suivant f

sorted(s, key = f, reverse = True) est la liste s triée par ordre décroissant suivant f

Par exemple, pour trier par ordre croissant suivant la valeur modulo 5

# def f(x):

   return x % 5 

 

s = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

s.sort(key = f)       alors s = [5, 10, 1, 6, 2, 7, 3, 8, 4, 9]

Par exemple, pour trier une liste de couples [x, y] par x croissants puis en cas d'égalité par y décroissants:

def g(x):

    return (x[0], -x[1])

 

t = [[1,2], [3,1], [1,3], [2,5], [2,4], [3,3]]

t.sort(key = g)  alors t = [[1, 3], [1, 2], [2, 5], [2, 4], [3, 3], [3, 1]]

13) Autres fonctions disponibles: minimum, maximum, somme

min(s) est le plus petit élément de la liste s

max(s) est le plus petit élément de la liste s

sum(s) est la somme des éléments de la liste s