On définit ainsi la structure d'une liste : il s'agit d'une autre liste contenant le même nombre d'éléments mais ceux-ci sont triés et à chaque élément on a fait correspondre un nouvel entier de manière à ce que la nouvelle liste ne contienne aucun trou, en partant de 0. Par exemple, la liste [6;2;5;1;2;3;5;1;2;6] devient lorsqu'elle est triée [1;1;2;2;2;3;5;5;6;6]. On associe alors 0 au plus petit nombre, 1 au suivant, etc... Donc 1 devient 0, 2 devient 1, 3 devient 2, 5 devient 3 et 6 devient 4. La structure de la liste est finalement : [0;0;1;1;1;2;3;3;4;4].
Pour cela, on va utiliser l'algorithme suivant (mais on pourrait avoir d'autres stratégies) :
- on trie la liste
- on enlève les éléments en plusieurs exemplaires dans le résultat, ce qui crée une liste appelée « référence ».
- en utilisant référence, on crée une fonction qui à un entier associe son nouveau représentant. Il suffit pour cela de chercher la position de l'entier dans la référence.
- on applique cette fonction à tous les éléments de la liste triée.

1) Ecrire une fonction qui prend une liste qu'on suppose triée (et donc deux objets égaux sont toujours côte à côte) et qui rend la même liste, avec les éléments dans le même ordre mais ne contenant plus qu'un exemplaire de chaque (par exemple, [1;1;1;2;3;3] devient [1;2;3]).
Solution

> Haut de la page