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 :

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 :

from graphviz import *

def permgraphe(perm):
	G = Graph(format="png")
	for i in perm:
		G.node(i)
	for i in range(len(perm)):
		for j in range(i+1,len(perm)):
			if perm[i]>perm[j]:
				G.edge(str(perm[i]),str(perm[j]))
	return G

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.

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

• Le tri par insertion est quadratique (programme de 1^re)
• Le tri par sélection est quadratique (programme de 1^re)
• 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.

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

from random import shuffle

def lpgsd(liste):
    n = 0
    files = []
    while len(liste):
         ok = False
         for file in files:
                 if file[0]>liste[-1]:
                         ok = True
                         file.insert(0,liste.pop())
                         break
         if not ok:
                 files.append([liste.pop()])
    return len(files)

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 :

N = 10
stats = []

for k in range(1000000):
    L = list(range(N))
    shuffle(L)
    stats.append(lpgsd(L))

on obtient ce genre de résultats :

qui suggère cette répartition :

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.

• La version liste circulaire :

  

• La version file :

  

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 :

class Enfant:
    
    def __init__(self, prenom):
        self.prenom = prenom
        self.gauche = None
        self.droite = None

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 :

pierre = Enfant('Pierre')
laure = Enfant('Laure')
anonyme = Enfant(1)

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.

class Ronde:
    
    def __init__(self):
        self.longueur = 0
        self.entree = None

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.

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 :

class Ronde:
    ...

    def initialiser(self, liste_prenoms):
        self.entree = Enfant(liste_prenoms[0])
        for prenom in liste_prenoms[1:]:
            nouveau = Enfant(prenom)
            self.inserer_a_gauche(self.entree, nouveau)

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

class Ronde:
    ...

    def inserer_a_gauche(self, ancien, nouveau):
        ancien.accueillir_a_gauche(nouveau)
        self.longueur += 1

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 :

class Enfant:
    ...
    
    def accueillir_a_gauche(self, nouveau):
        self.gauche.droite = nouveau
        nouveau.gauche = self.gauche
        nouveau.droite = self
        self.gauche = nouveau

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 :

class Enfant:
    
    def __init__(self, prenom):
        self.prenom = prenom
        self.gauche = self
        self.droite = self

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

class Ronde:
    ...

    def reduire(self):
        while self.longueur > 1:
            cible = self.entree
            for _ in range(self.pas - 1):
                cible = cible.droite
            self.entree = cible.droite
            self.supprimer(cible)

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 :

class Ronde:
    ...

    def demande_de_quitter(self, enfant):
        enfant.se_retire()
        self.longueur -= 1

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 :

class Enfant:
    ...

    def se_retire(self):
        self.droite.gauche = self.gauche
        self.gauche.droite = self.droite
        self.gauche = self
        self.droite = self

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 ?

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 :

class Enfant:
    
    def __init__(self, prenom, suivant=None):
        self.prenom = prenom
        self.suivant = suivant    

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

class File:
    
    def __init__(self):
        self.tete = None
        self.queue = None
        self.longueur = 0

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.

class File:
    ...
    
    def arrivee(self, nouveau):
        if self.est_vide():
            self.tete = nouveau
        else:
            self.queue.suivant = nouveau
        self.queue = nouveau
        self.longueur += 1

    def avance(self):
        if not self.est_vide():
            depart = self.tete
            self.tete = depart.suivant
            self.longueur -= 1
            if self.est_vide():
                self.queue = self.tete
            return depart        

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

class File:    
    ...
    
    def reduire(self):
        while self.longueur > 1:
            for _ in range(self.pas - 1):
                self.arrivee(self.avance())
            self.avance()

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é :

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] ?

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 :

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

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 :

def flavius(n):
    queue = list(range(n))
    while len(queue)>1:
        queue.append(queue.pop(0))
        queue.pop(0)
    return queue.pop(0)

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]