Sujets sur les listes, files et piles

comptines, rondes, jeux de massacre, tri...
vendredi 13 novembre 2020
par  Alain BUSSER , Sébastien HOARAU

Les listes, files et piles constituent une partie importante du programme de terminale en NSI [3]. Dans cet article on va voir le cas emblématique d’un des plus vieux problèmes de mathématiques « récréatives » connues, et l’utilisation de files pour trier des entiers en parallèle. Voici par exemple comment on peut trier 5 entiers avec 3 files, en ne défilant qu’à la fin :

Piles

Voici un devoir sur les piles et leur utilisation en Forth (langage) :

Pour aller plus loin, on peut également programmer en PostScript [1] et même y faire un peu de Sofus :

Et ce jeu de Donald Knuth permet de se familiariser avec la notion de pile. Il s’agit d’utiliser une pile pour trier des nombres.

Tri par files

Une variante du jeu précédent est inspirée par le sujet donné au concours ENS en 2011, lequel montre comment on peut trier des entiers avec plusieurs [2] files :

Un invariant de l’algorithme est « toutes les files sont triées ».

Exemple

Par exemple pour trier la liste 4,2,1,5,3 (une permutation des 5 premiers entiers), on a besoin de 3 files. Au départ les files sont vides :

L’élément 3 peut donc être placé sur n’importe laquelle de ces files, par exemple celle du haut (la bleue) :

L’invariant impose que l’élément 5 ne soit pas placé sur la même file car sinon, en bout de compte, il serait défilé après le 3 et donc placé avant. On peut le placer sur la file 2 (verte) par exemple :

L’élément 1, a contrario, peut être placé sur n’importe quelle file, car il est plus petit que les éléments y figurant déjà. Par exemple on peut l’ajouter à la file bleue :

2 est plus grand que 1 et ne peut donc plus être placé sur la file bleue. Par contre il est plus petit que 5 et peut être placé sur la file verte :

Jusqu’ici on s’en tirait avec seulement 2 files. Mais 4 est à la fois plus grand que 1 et que 2, et la file du bas (rouge) est donc nécessaire pour accueillir ce 4 :

Au moment où on a placé le 5 sur la file verte, on aurait pu le défiler immédiatement puisqu’il était déjà à sa place. Mais cela ne change rien (le sujet demandait de le prouver) si on préfère attendre que la liste de départ soit vide, pour défiler tout. En commençant bien entendu par le 5 :

En attribuant à chaque nombre de la permutation de départ, la couleur de la file qu’il a traversée au cours du tri, on obtient une coloration d’un graphe :

Mais quel est ce mystérieux graphe ?

Graphes de permutation

Il s’agit d’un graphe de permutation. Il représente la relation symétrique « est inversé avec ». Par exemple dans la permutation 4,2,1,5,3 on constate que 4 est placé avant 2 (alors qu’il est plus grand que 2), alors il y a une arête entre 2 et 4 sur le graphe ci-dessus.

Pour dessiner un graphe de permutation, on peut donc utiliser la fonction Python suivante :

  1. from graphviz import *
  2.  
  3. def permgraphe(perm):
  4.         G = Graph(format="png")
  5.         for i in perm:
  6.                 G.node(i)
  7.         for i in range(len(perm)):
  8.                 for j in range(i+1,len(perm)):
  9.                         if perm[i]>perm[j]:
  10.                                 G.edge(str(perm[i]),str(perm[j]))
  11.         return G

Télécharger

Par exemple avec la permutation 6,3,1,7,5,9,8,2,4 de l’énoncé ENS Lyon, on obtient le graphe suivant :

Or le tri de cette liste

passe par ce remplissage de files :

pour finir le tri :

Et on constate que la coloration par les files du graphe précédent est une coloration propre :

Ce résultat est général, mais les graphes de permutation ne sont pas souvent connexes.

Complexité

Des résultats sont au programme de NSI, sur la complexité de certains algorithmes de tri :

  • Le tri par insertion est quadratique (programme de 1re)
  • Le tri par sélection est quadratique (programme de 1re)
  • Le tri fusion est en n×log(n) (un des exemples possibles en Tle, à propos de la méthode « diviser pour régner »).

Il est alors naturel de se demander quelle est la complexité du tri par files. Si on dispose de k files pour trier une liste de n entiers :

  • on va n fois effectuer un enfilement (vers une des k files) depuis la liste de départ
  • on va n fois effectuer un défilement (depuis une des k files) vers la liste d’arrivée.
  • mais avant chaque enfilement on cherche où enfiler, ce qui nécessite de chercher la première file qui restera triée après l’enfilement : linéaire par rapport à k ; et avant chaque défilement on cherche le plus grand des éléments défilables, qui est celui qu’on défile : là encore complexité linéaire par rapport à k.

En résumé, le tri en utilisant k files est linéaire par rapport à k et par rapport à n.

Mais dans le pire cas (liste triée dans l’ordre décroissant) on a besoin de n files (k=n) et du coup, la complexité de cet algorithme de tri est quadratique.

nombre de files nécessaires

Il est rare que beaucoup de files soient nécessaires, parce que peu de permutations nécessitent beaucoup (environ n) de files. Pour étudier la répartition statistique des nombres de files, on répète un grand nombre de fois l’opération de mélanger (shuffle) au hasard une liste puis la trier en comptant les files qui ont été nécessaires à ce tri. L’algorithme est basé sur le fait que le nombre de files nécessaires est égal à la longueur de la plus grande sous-suite décroissante. On calcule cette longueur tout simplement en comptant les files, dans une fonction lpgsd (longueur de la plus grande sous-suite décroissante) :

  1. from random import shuffle
  2.  
  3. def lpgsd(liste):
  4.     n = 0
  5.     files = []
  6.     while len(liste):
  7.          ok = False
  8.          for file in files:
  9.                  if file[0]>liste[-1]:
  10.                          ok = True
  11.                          file.insert(0,liste.pop())
  12.                          break
  13.          if not ok:
  14.                  files.append([liste.pop()])
  15.     return len(files)

Télécharger

Pour voir quelle est la répartition statistique avec une liste de 10 éléments, avec une répétition sur un million d’expériences :

  1. N = 10
  2. stats = []
  3.  
  4. for k in range(1000000):
  5.     L = list(range(N))
  6.     shuffle(L)
  7.     stats.append(lpgsd(L))

Télécharger

on obtient ce genre de résultats :

nombre de files fréquence (en pourcent)
0 0
1 0.4681
2 15.7452
3 44.1761
4 30.2746
5 8.2044
6 1.0587
7 0.0702
8 0.0027
9 0.0

qui suggère cette répartition :

0123456789

Le cas 3 files est le plus fréquent, et il est rare d’avoir besoin de plus de 4 files.

Plouf-Plouf...

Le problème original est connu sous le nom de problème de Josèphe. Il s’agit d’un problème de permutation lié à des formulettes d’élimination. C’est d’ailleurs cette version plus pacifique que nous allons illustrer ici, comme l’indique le titre de la section.

Plouf Plouf par Raphaëlle H.

L’origine historique du problème de Josèphe n’est pas complètement déterminée. On l’attribue à Flavius Josèphe, historiographe judéen du Ier siècle, ayant beaucoup écrit sur les conflits de son temps entre Rome et Jérusalem, mais le travail de Laurent Signac [3] conclut que c’est probablement les Problèmes plaisants et délectables de C.G. Bachet [4] qui ont fait connaître le problème de Josèphe.

Introduction

Description wikipédia

Le plouf-plouf (ou pouf-pouf, ou ploum-ploum, ou pia-pia, ou trou-trou etc.) permet de choisir un joueur en éliminant successivement tous les autres. Un des participants joue le rôle de meneur. Tous les enfants se mettent en cercle,
[...]
Le meneur chante une comptine, en pointant du doigt successivement tous les enfants du cercle à chaque temps de la comptine. L’enfant désigné en dernier est éliminé, et le processus recommence avec les participants restants.

But

Nous allons modéliser cette activité enfantine par des objets informatiques au sens de la Programmation Orientée Objets, un des thèmes de chapitre du programme de la spécialité NSI en Terminale [5].

Nous verrons deux modélisations. La première colle au sujet original : il s’agit d’une ronde, avec une entrée (celle désignée par le meneur). La seconde transforme cette ronde en file indienne. Dans les deux cas, un type abstrait de données (TAD) sera à l’honneur.

En disposant de cartes, on peut même en faire un tour de magie.

Les codes complets

  • La version liste circulaire :
  • La version file :

Une liste circulaire

Comme le problème parle d’une ronde, la première idée qui semble naturelle c’est d’essayer de modéliser cette ronde.

Deux objets : l’enfant et la ronde

L’enfant

Dans ce jeu, l’enfant est dans une ronde. Nous avons besoin de l’identifier, par son prénom par exemple. Il a un voisin à sa gauche (bleu pour les petits qui ne maîtrise pas encore le concept de gauche-droite) et un sa droite (rouge).

Voici comment en Python on peut définir un enfant :

  1. class Enfant:
  2.    
  3.     def __init__(self, prenom):
  4.         self.prenom = prenom
  5.         self.gauche = None
  6.         self.droite = None

Télécharger

Sans nous attarder pour le moment sur les détails syntaxiques (__init__, self) on peut simplement constater que l’objet informatique Enfant est bien constitué d’un prenom et de deux voisins, non définis. L’enfant qui n’est pas dans une ronde n’a, en effet, pas de voisins. Le None représente le rien en Python [6].

La création d’un nouvel Enfant (informatique) se fait par l’appel à la fonction Enfant(), en lui passant un prénom en argument. Quelques exemples :

  1. pierre = Enfant('Pierre')
  2. laure = Enfant('Laure')
  3. anonyme = Enfant(1)

Télécharger

La ronde

Elle est définie par une entrée (l’enfant pointé par le meneur) et un nombre d’enfants. On peut aussi, mémoriser le nombre d’enfants de cette ronde. Lorsqu’on décide de créer une ronde, au départ elle est vide.

  1. class Ronde:
  2.    
  3.     def __init__(self):
  4.         self.longueur = 0
  5.         self.entree = None

Télécharger

Il va falloir la remplir des enfants présents. Dans la vraie vie, cette ronde se constitue dans un joyeux désordre, chaque enfant se plaçant comme il veut. En informatique il est plus simple d’organiser un peu les choses. Nous allons intégrer les enfants un par un :

  • d’abord l’entrée, ie l’enfant pointé par le meneur
  • puis les autres, en les insérant à la gauche de cette entrée.

Avant de présenter les opérations sur notre ronde d’enfants, et notamment son remplissage ordonné, voici une représentation simplifiée d’une ronde de 5 enfants dont les prénoms ont été réduits à des numéros. Cette ronde a été créée par un appel Ronde() puis initialiser avec 5 enfants, cette opération est décrite dans le bloc suivant.

Les actions

Initialiser la ronde

Nous avons déjà évoqué cette opération : il s’agit, à partir d’une liste de prénoms, d’insérer un à un les nouveaux enfants à gauche de l’entrée :

  1. class Ronde:
  2.     ...
  3.  
  4.     def initialiser(self, liste_prenoms):
  5.         self.entree = Enfant(liste_prenoms[0])
  6.         for prenom in liste_prenoms[1:]:
  7.             nouveau = Enfant(prenom)
  8.             self.inserer_a_gauche(self.entree, nouveau)

Télécharger

self ici désigne la ronde elle-même. La ronde tente d’insérer en son sein, un nouveau à gauche d’un enfant déjà en place. inserer_a_gauche procède comme suit :

  • la ronde demande à l’ancien d’accueillir le nouveau comme voisin de gauche
  • la ronde incrémente son nombre d’enfants de 1

Et c’est tout. On touche ici un principe fondamental de la POO : les objets se transmettent des ordres, ou plus poliment, des messages. Ainsi la définition de la méthode inserer_a_gauche est extrêmement simple, reportant une partie du travail sur un autre objet (un Enfant) :

  1. class Ronde:
  2.     ...
  3.  
  4.     def inserer_a_gauche(self, ancien, nouveau):
  5.         ancien.accueillir_a_gauche(nouveau)
  6.         self.longueur += 1

Télécharger

Accueillir un nouveau

Revenons donc à l’enfant qui doit accueillir un nouveau à sa gauche dans la ronde. Pour cela il lui faut effectuer les étapes suivantes (que l’on peut tenter de faire trouver en faisant l’opération dans une vraie ronde) :

  1. Présenter le nouveau comme le voisin de droite de son voisin de gauche
  2. Présenter son voisin de gauche comme étant le voisin de gauche du nouveau
  3. Se présenter comme le voisin de droite du nouveau
  4. Prendre le nouveau comme voisin de gauche

Dans cet algorithme décrit en français, c’est l’enfant qui fait l’accueil qui parle dans la version pythonesque, ce sujet est représenté par le mot-clé self. La méthode accueillir_a_gauche pour un Enfant :

  1. class Enfant:
  2.     ...
  3.    
  4.     def accueillir_a_gauche(self, nouveau):
  5.         self.gauche.droite = nouveau
  6.         nouveau.gauche = self.gauche
  7.         nouveau.droite = self
  8.         self.gauche = nouveau

Télécharger

De la difficulté à rompre l’isolement...

Si vous avez été attentif, vous aurez noté que cela ne fonctionne pas. En effet, lorsqu’on crée l’entrée, ie l’insertion dans la ronde du premier enfant, celui-ci n’a pas de voisins. Dès lors, au moment d’accueillir le second, notre enfant isolé ne peut pas effectuer l’étape 1 : il n’a pas de voisin de gauche. Pour régler le souci, le plus simple est de dire qu’un enfant isolé peut se considérer comme ses propres voisins, dans une ronde où il est seul.

Ce qui nous donne une nouvelle définition de notre Enfant informatique :

  1. class Enfant:
  2.    
  3.     def __init__(self, prenom):
  4.         self.prenom = prenom
  5.         self.gauche = self
  6.         self.droite = self

Télécharger

Dès lors l’accueil d’un deuxième n’est plus un souci. Ci-dessous illustré l’accueil du petit Cinq à gauche de Un :

Nous avons de gauche à droite les différentes étapes. D’abord la création du nouveau (5), puis les étapes vues précédemment :

  1. L’ancien (1) qui doit accueillir à sa gauche commence par présenter 5 comme le voisin de droite de son voisin de gauche 4 ;
  2. puis 1 dit à 5 : « voici 4 mon voisin de gauche, prend le comme voisin de gauche » ;
  3. 1 se présente comme le nouveau voisin de droite de 5 ;
  4. 1 prend 5 comme voisin de gauche.

Résoudre le problème

Résoudre le problème c’est effectuer la réduction de la ronde jusqu’à n’avoir plus qu’un enfant. Nous devons effectuer les tâches suivantes :

  1. A partir de l’enfant point d’entrée, il nous faut, grâce au pas (qui est le nombre de temps de la comptine) trouver l’enfant qui devra quitter de la ronde
  2. Demander à l’enfant de quitter la ronde
  3. Déplacer l’entrée de la ronde à la droite de l’enfant retiré
  4. Recommencer au 1 jusqu’à ce qu’il n’y ait plus qu’un seul enfant dans le cercle

Ce qui, remis dans un ordre différent donne :

Tant que le cercle comporte plus d’un enfant :

  • on avance de pas enfants vers la droite à partir de l’entrée de la ronde
  • on place l’entrée de la ronde à droite de cet enfant
  • l’enfant sélectionné quitte la ronde

Il ne vous aura pas échappé que pour l’instant il n’a jamais été question de pas dans notre ronde. C’est effectivement une information manquante, qu’il faut mémoriser lors de la création de la Ronde. Nous prendrons ici une valeur par défaut de 2.

Et voici la traduction Python dans une méthode de notre classe Ronde :

  1. class Ronde:
  2.     ...
  3.  
  4.     def reduire(self):
  5.         while self.longueur > 1:
  6.             cible = self.entree
  7.             for _ in range(self.pas - 1):
  8.                 cible = cible.droite
  9.             self.entree = cible.droite
  10.             self.supprimer(cible)

Télécharger

A l’instar de la méthode d’insertion, demander à un enfant se quitter la ronde consiste à :

  1. demander à l’enfant de se retirer, sans rompre le cercle
  2. décrémenter de 1 la longueur de la ronde

On pourrait aborder le cas particulier du cercle à 1 élément et qui se retrouve donc vide... mais dans le cadre de ce problème, nous avons vu que le cercle contiendra toujours au moins 1 enfant. Nous pouvons donc ignorer ce cas particulier ce qui simplifie les choses. Voici la méthode de la classe Ronde :

  1. class Ronde:
  2.     ...
  3.  
  4.     def demande_de_quitter(self, enfant):
  5.         enfant.se_retire()
  6.         self.longueur -= 1

Télécharger

On pourrait réaliser une activité débranchée pour faire découvrir les étapes à suivre pour qu’un enfant se retire du cercle, sans que ce dernier ne soit rompu. Voilà ces étapes :

  1. L’enfant dit à son voisin de droite : « ton nouveau voisin de gauche est mon voisin de gauche »
  2. L’enfant dit à son voisin de gauche : « ton nouveau voisin de droite est mon voisin de droite »
  3. L’enfant se prend pour voisin de gauche et droite

Ce qui nous donne en Python :

  1. class Enfant:
  2.     ...
  3.  
  4.     def se_retire(self):
  5.         self.droite.gauche = self.gauche
  6.         self.gauche.droite = self.droite
  7.         self.gauche = self
  8.         self.droite = self

Télécharger

Conclusion

Nous avons maintenant complété notre modèle. On ne peut que constater la facilité d’écriture de la programmation objets qui permet de traduire presque mot à mot les actions à réaliser sur les objets du monde réel. La classe Ronde accompagnée de la classe Enfant implémente ici un type abstrait de données liste chaînée. Il s’agit d’une liste circulaire doublement chaînée. Cette structure est hors programme de NSI. Ne pourrait-on pas modéliser par une autre structure de données ?

Une file indienne

Type abstrait de données

Imaginons le meneur debout devant la file d’enfants : pendant qu’il égrène les temps de la comptine, il demande à l’enfant en tête de file d’aller se placer derrière. Lorsque la comptine s’achève, l’enfant de tête est éliminé.

La modélisation

Dans une file, l’enfant est toujours identifié par son prénom, mais il n’a plus de voisins à sa gauche et à sa droite. Il a un voisin devant lui dans la file et un voisin derrière lui : un précédent et un suivant. On pourrait modéliser les deux. On retombe sur une structure doublement chaînée, qui est hors programme officiel de NSI [3]. Peut-on choisir une seule liaison entre les personnes de la file ?

Pour faire le bon choix, il nous faut voir les opérations à effectuer sur une file.

Arrivée dans une file

  1. La queue de la file doit dire que son suivant est ce nouveau
  2. De plus, en cas de file vide au départ, la tête c’est aussi ce nouveau
  3. On a une personne de plus dans la file

La file avance

  1. Si la file n’est pas vide : la tête de file devient le suivant de la tête
  2. Si la file ne contenait qu’un seul élément, on doit aussi déplacer la queue de la file.

Si chaque individu de la file mémorise le précédent, on constate que faire avancer la file est moins évident. En effet, comment dire à la tête de pointer la personne derrière elle ? Il faudrait alors partir de la queue de la file et avancer jusqu’à ce que le précédent soit la tête. Le choix de modéliser le suivant s’avère donc le meilleur.

Nos nouveaux objets

On garde donc le suivant comme liaison entre les individus :

  1. class Enfant:
  2.    
  3.     def __init__(self, prenom, suivant=None):
  4.         self.prenom = prenom
  5.         self.suivant = suivant    

Télécharger

Et la file d’attente est caractérisée par la tête de file et la queue de la file :

  1. class File:
  2.    
  3.     def __init__(self):
  4.         self.tete = None
  5.         self.queue = None
  6.         self.longueur = 0

Télécharger

Dans une file d’attente, une nouvelle arrivée se met à la queue. Avec le cas particulier que si la file était vide, la tête et la queue sont la même personne. Pour l’avancée de la file, la file ne doit pas être vide.

  1. class File:
  2.     ...
  3.    
  4.     def arrivee(self, nouveau):
  5.         if self.est_vide():
  6.             self.tete = nouveau
  7.         else:
  8.             self.queue.suivant = nouveau
  9.         self.queue = nouveau
  10.         self.longueur += 1
  11.  
  12.     def avance(self):
  13.         if not self.est_vide():
  14.             depart = self.tete
  15.             self.tete = depart.suivant
  16.             self.longueur -= 1
  17.             if self.est_vide():
  18.                 self.queue = self.tete
  19.             return depart        

Télécharger

La résolution

  1. on fait défiler les enfants autant de fois que nécessaire
  2. on élimine l’enfant désigné par la comptine
  3. on recommence jusqu’à qu’il ne reste qu’un enfant
  1. class File:    
  2.     ...
  3.    
  4.     def reduire(self):
  5.         while self.longueur > 1:
  6.             for _ in range(self.pas - 1):
  7.                 self.arrivee(self.avance())
  8.             self.avance()

Télécharger

Animation

En utilisant le module graphviz il est possible de générer des graphes orientés (objet Digraph) qu’on peut mettre à jour à chaque étape. Les images ainsi obtenues, permettent la création d’une petite animation. Avec 7 protagonistes (enfants ou chevaliers), et un pas de 2, le survivant porte le numéro 7.

  1. La file de départ : 1 en tête de file, 7 à la queue :
  2. Le pas étant de 2, 1 est invité à passer derrière, 2 se retrouve en tête :
  3. 2 est éliminé, 3 se retrouve en tête...
  4. ...et passe à l’arrière puisque le meneur compte Un sur lui, 4 se retrouve en tête :
  5. et le meneur compte Deux, 4 est éliminé :
  6. et ainsi de suite...

L’ensemble animé :

Conclusion

Nous avons vu, grâce à ce petit problème d’élimination la possibilité de manipuler deux structures de données abstraites : une liste circulaire doublement chaînée et une file. La programmation orientée objets autorise une description (relativement) naturelle des propriétés et des actions de nos objets réels.

Ce type de modélisation peut-il faire l’objet d’une séance d’introduction à presque tous les thèmes du chapitre Structures de Données du programme de la spécialité NSI de Terminale [3] ?

et sans objets ?

En fait, dès lors qu’on n’utilise que ses méthodes pop(0) (retrait en tête de file) et append (rajout en queue de file) une liste de Python se comporte comme une file.

Le mot file étant réservé en Python (c’est un fichier), on appellera queue la file en question (comme dans l’expression « faites la queue » sauf qu’ici le gagnant du jeu est celui qui a réussi à faire la queue le plus longtemps possible). Alors

  • sortir un joueur de la file (celui qui est en tête), se fait par queue.pop(0)
  • renvoyer le premier faire la queue, se fait donc par queue.append(queue.pop(0))

Le déroulé sera décrit par cette fonction :

  1. def flavius(n):
  2.     queue = list(range(n))
  3.     while len(queue):
  4.         queue.append(queue.pop(0))
  5.         print(queue.pop(0),"éliminé")

Télécharger

Avec 7 personnes au départ (numérotées de 0 à 6) on a ce scénario (obtenu par l’appel flavius(7)) :

1 éliminé
3 éliminé
5 éliminé
0 éliminé
4 éliminé
2 éliminé
6 éliminé

Pour avoir quelque chose de plus « fonctionnel » on peut effectuer ces modifications :

  1. def flavius(n):
  2.     queue = list(range(n))
  3.     while len(queue)>1:
  4.         queue.append(queue.pop(0))
  5.         queue.pop(0)
  6.     return queue.pop(0)

Télécharger

L’affichage de flavius(7) donne alors simplement 6. Mais comme on a une fonction, on peut afficher plusieurs de ses valeurs, par exemple avec

print([flavius(n) for n in range(1,13)])

qui donne

[0, 0, 2, 0, 2, 4, 6, 0, 2, 4, 6, 8]

puis représenter graphiquement cette fonction (par exemple avec matplotlib) ou rajouter des pop(0) pour les variantes du problème...

Bref, beaucoup d’expérimentations possibles avant même de se poser la question de l’efficacité de l’algorithme [7]


[1Avec la commande gs qui lance un interpréteur Ghostscript. Au passage on y gagne aussi un graphisme tortue.

[2Avec une seule file aussi on peut effectuer un tri.

[3SIGNAC, Laurent. Autour du problème de Josèphe. Bibnum. Textes fondateurs de la science, 2012.

[4Bachet, C. G., & Labosne, A. (1874). Problemes plaisants & delectables qui se font par les nombres. Gauthier-Villars

[5Programme de Numérique et Sciences Informatiques de Terminale Générale, Bulletin Officiel de l’Éducation Nationale, n°8 du 25 juillet 2019

[6voir par exemple Python et le taoïsme un article zen.

[7Voir ici pour en savoir plus.


Commentaires

Navigation

Articles de la rubrique