PRFO23 : TP5

Exercice 1 : Interface des ensembles

Reprendre le fichier set.mli des TPs précédents.

Exercice 2 : Implémentation à l'aide d'arbres binaires de recherche bien équilibrés

Dans un nouveau fichier set.ml, implémenter les ensembles à l'aide des arbres binaires de recherche équilibrés à l'aide de la méthode AVL.

Exercice 3 : Utilisation, ensemble de permutations

Étant donné un ensemble s : 'a set, une permutation sur s est une liste de type 'a list contenant les éléments de s dans un certain ordre. On cherche à calculer l'ensemble des permutations de s.

1. Écrire une fonction de type 'a set -> 'a list set qui renvoie l'ensemble des permutations de son paramètre. On pourra utiliser l'algorithme suivant :

   perm(s):
     si s est vide
       retourner l'ensemble contenant la liste vide
     sinon
       r ← ∅
       pour tout x dans s
         r ← r ∪ { x::l | l ∈ perm(s \ { x } }
       retourner r
   

   (Bien entendu, on n'utilisera pas de trait impératif, mais on utilisera un fold.)
2. Tester la fonction à partir d'un ensemble de chaînes de caractères.