Exercice 1 : List et Random

On se propose d'écrire une fonction pour permuter aléatoirement les éléments d'une liste. Plusieurs méthodes existent, ici nous allons nous inspirer du tri rapide, mais avec une fonction de comparaison en quelque sorte aléatoire. L'algorithme procède ainsi :

• partitionner la liste en deux listes. Chaque élément est placé avec la même probabilité dans une des deux listes,
• permuter aléatoirement les deux listes par induction,
• concaténer les deux listes ainsi mélangée.

Écrire cet algorithme en utilisant la fonction Random.bool et des fonctions du module List.

Exercice 2 : Enlever les éléments dupliqués d'une liste.

Étant donné une liste de $n$ entiers, on souhaite retirer les doublons de cette liste, de sorte que chaque entier apparaisse au plus une fois.

• Donner un algorithme de complexité $O(n^2)$.
• On parcourt maintenant la liste de gauche à droite, en gardant les entiers déjà lus dans une structure d'ensemble (Set). Écrire cet algorithme. Quelle est sa complexité ?
• Faire de cet algorithme un foncteur, pour l'utiliser sur des listes de n'importe quel type ordonné.

Exercice 3 : Compter les mots d'un roman

Écrire un programme qui lit l'entrée standard et compte le nombre de mots distincts. On considère qu'un mot est une suite de caractères entre deux espacements. Pour cela on utilisera la fonction Scanf.scanf " %s".

Attention, lorsque cette fonction arrive en fin de l'entrée, la chaîne lue est "", mais elle ne lance pas d'exceptions.