Tutoriel en pdf pour apprendre Caml


Télécharger Tutoriel en pdf pour apprendre Caml

★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


La lettre de Caml numéro 2

Laurent Chéno

54, rue Saint-Maur

75011 Paris

Tél. (1) 48 05 16 04

Fax (1) 48 07 80 18 email: novembre 1995

Edito´

Dans ce numéro, qui a pris un peu de retard (mais mes copies s’accumulent...), vous trouverez un texte de notre gourou commun, Pierre Weis, qui nous parle avec le talent que nous lui connaissons d’évaluation paresseuse, nous donne une implémentation en Caml, et des applications édifiantes.

Ensuite vous trouverez quelques exemples simples de programmation en Caml, beaucoup moins ambitieux que ce que nous expose P. Weis, qui pourraient servir d’exercices dans nos classes: on s’intéresse particulièrement a` un peu de combinatoire sur des mots sur {?1,1} ou {0,1}, et aux permutations de {1,2,...,n}.

Rien de génial, mais une mine d’exercices possibles.

La distribution de cette lettre est en défaut, je le sais bien, et j’essaie d’y remédier. Mais les cours, les copies, et maintenant les grèves de transport, tout cela me fait trop souvent reporter au lendemain ce que j’aurais aimé achever plus vite.

Raison de plus pour espérer plus nombreuses vos idées d’articles, même courts, et pas forcément super-géniaux...

Table des matières

1    Un article de Pierre Weis sur l’e´valuation paresseuse 3

1.1    Programmation paresseuse en Caml          . . . . . . . . . . . . . . . .                3

1.2    Illustration de la programmation paresseuse: les séries entières .            5

2    Un peu de combinatoire des mots             8

2.1    Mots de Lukasiewicz, nombres de Catalan . . . . . . . . . . . . .   8

2.1.1   Définition et propriétés des mots de Lukasiewicz      . . . . .       8

2.1.2   Nombres de Catalan . . . . . . . . . . . . . . . . . . . . .           9

2.2    Mots de Lyndon, ordre lexicographique . . . . . . . . . . . . . . .    12

3    Permutations         15

3.1    La représentation choisie ici . . . . . . . . . . . . . . . . . . . . .             15

3.2    Quelques fonctions simples . . . . . . . . . . . . . . . . . . . . . .              15

3.3    Le problème de la génération des permutations . . . . . . . . . .          18

3.3.1   Génération récursive de l’ensemble des permutations . . .       18

3.3.2   Une méthode tout a` fait différente . . . . . . . . . . . . .           18

Un article de Pierre Weis sur l’évaluation paresseuse

Programmation paresseuse en Caml

La programmation paresseuse consiste a` différer l’évaluation de certaines parties d’un programme jusqu’a` ce que cette évaluation soit absolument nécessaire à la poursuite des calculs. Cela permet de procéder à des calculs incrémentaux, et autorise la définition de structures de données potentiellement infinies. Je donne un codage simple de l’évaluation paresseuse en Caml, et une application frappante: la définition et la manipulation de séries entières en Caml.

En Caml, le régime d’évaluation est l’appel par valeur c’est-à-dire que l’évaluation est effectuée sans retard (on dit aussi que le langage est strict). Les autres régimes d’évaluation classiques des langages de programmation sont l’appel par nom et l’appel par nécessité. Tous deux consistent a` retarder l’évaluation des arguments des fonctions: on appelle le code de la fonction sans avoir évalué ses arguments. Ces arguments seront évalués dans le corps de la fonction, si leur valeur est indispensable au calcul du résultat de la fonction. Par exemple si l’argument fonction n’est pas (resp. pas toujours) utilisé dans le corps de la fonction, il ne sera jamais calculé (resp. calculé que s’il est utilisé). Techniquement l’argument non évalué est appelé glac¸on ou suspension; il est passé a` la fonction qui l’évalue au besoin en forc¸ant (ou dégelant) le glac¸on. La différence entre ces deux modes d’évaluation paresseuse concerne le nombre d’évaluations possibles des gla¸cons: en évaluation par nom, les glac¸ons sont dégelés (donc réévalués) chaque fois qu’on a besoin de leur valeur; au contraire, avec l’évaluation par nécessité on ne calcule la valeur d’un glac¸on qu’une fois au plus: on profite du dégel du glac¸on pour enregistrer la valeur calculée; ensuite toute nouvelle tentative de dégel du glac¸on ne fait que retourner cette valeur enregistrée. D’un point de vue efficacité, l’appel par nécessité semble clairement gagnant: c’est en général vrai, sauf si le stockage des valeurs calculées se révèle excessivement couˆteux en mémoire.

Nous allons implémenter l’appel par nécessité, en commen¸cant par définir le type polymorphe des glac¸ons: un gla¸con encore gelé est représenté par une fonction a` zéro argument, qui donnera sa valeur quand on la déclenchera.

type ’a glac¸on = | Gelé of unit -> ’a

| Connu of ’a;;

Type glac¸on defined.

Nous sommes maintenant armés pour définir les listes paresseuses en queue: la queue de ces listes est évaluée paresseusement.

type ’a lazylist = | Nil | Cons of ’a cellule and ’a cellule = { hd : ’a; mutable tl : ’a lazylist glac¸on};;

 

La gestion de l’appel par nécessité est faite par une fonction annexe qui dégèle les glac¸ons, calcule leur valeur et la stocke en mémoire:

let force cellule = let glac¸on = in match glac¸on with

| Connu val -> val

| Gelé g -> let val = g () in

<- Connu val; val;;

Nous définissons une fonctionnelle habituelle sur les listes: un map paresseux qui suspend le calcul sur la queue de la liste.

let rec lazymap f = function

 

| Nil -> Nil

| Cons ({hd = x;} as cellule) ->

 

Cons {hd = f x; tl = Gelé (function () -> lazy map f (force cellule))};; lazymap : (’a -> ’b) -> ’a lazylist -> ’b lazylist = <fun>

 

Définir la liste potentiellement infinie des nombres entiers consiste maintenant à donner le premier élément de cette suite, puis le moyen d’en calculer le reste: il suffit pour cela d’appliquer la fonction successeur aux éléments déjà calculés ...

let rec nat = Cons {hd = 0; tl = Gelé (fun () -> lazymap succ nat)};; nat : int lazylist = Cons {hd=0; tl=Gelé <fun>}

 

Pour parcourir ces suites potentiellement infinies (par exemple en vue de les imprimer) il faut définir une fonctionnelle analogue a` dolist; une précaution cependant, sous peine de boucler, cette fonctionnelle ne doit pas tenter de parcourir systématiquement toute la liste; c’est pourquoi on lui donne un argument numérique supplémentaire qui arrête arbitrairement le calcul au bout d’un certain nombres d’éléments visités.

let rec lazy do list f n = function

| Nil -> ()

| Cons ({hd = x; } as cellule) -> if n > 0 then begin f x; lazy do list f (n - 1) (force cellule) end;;

 

lazy do list : (’a -> ’b) -> int -> ’a lazylist -> unit = <fun>

 

Notez bien l’effet mémoire impliqué par l’impression des premiers éléments de la liste nat: les gla¸cons ont été dégelés à la demande jusqu’a` la profondeur voulue.

lazy do list printint 3 nat;;

 

012- : unit = ()

nat;;

- : int lazylist =

 

Cons

{hd=0; tl=

Connu

(Cons

{hd=1; tl=

Connu

(Cons

{hd=2; tl=

Connu

(Cons

{hd=3; tl=Gelé <fun>})})})}

Illustration de la programmation paresseuse : les séries entières

On peut tirer avantage de ces listes paresseuse pour implémenter des objets mathématiques eux aussi potentiellement infinis, donc a priori hors d’atteinte d’un calcul normal. Je vous propose de le faire pour les séries entières.

Pour cela nous utiliserons les grands nombres de Caml (la bibliothèque camlnum, qui implémente les nombres rationnels au sens des mathématiques, c’està-dire sans erreurs de calculs). Sous Unix, on accède à cette bibliothèque par la commande

$camllight camlnum

Commenc¸ons donc par ouvrir le module des grand nombres, et par définir un imprimeur pour ce nouveau type. Nous le définissons comme l’imprimeur par défaut des valeurs du type num en le déclarant au système interactif par la directive installprinter.

 

(* Utilitaires sur les grands nombres *) #open "num";;

(* Impression *) #open "format";; let print num n = printstring (string of num n);; install printer "printnum";;

Pour simplifier l’écriture nous redéfinissons les symboles arithmétiques habituels pour qu’ils opèrent sur les num

let prefix + = prefix +/ and prefix - = prefix -/ and prefix * = prefix */ and prefix / = prefix // and prefix >= = prefix >=/ and prefix = = prefix =/;;

(* Quelques constantes *) let un = num of int 1;; let zéro = num of int 0;; let moins un = zéro - un;;

Le type des séries entières (potentiellement infinies) est analogue a` celui des cellules de listes paresseuses, et réutilise le type des glac¸ons.

type ’a glac¸on = | Gelé of unit -> ’a | Connu of ’a;;

type série = {Constante : num; mutable Reste : série glac¸on};;

On définit donc de même l’accès au reste d’une série avec dégel et mise à jour pour le partage des calculs.

let reste de série s = match s.Reste with | Connu rest -> rest

| Gelé r -> let rest = r () in s.Reste <- Connu rest; rest;;

La suspension automatique des calculs étant gérée, il n’y a aucune difficulté a` définir les opérations usuelles sur les séries entières:

let rec addsérie s1 s2 =

 

{Constante = s1.Constante + s2.Constante;

Reste =

Gelé

(function () -> add série (reste de série s1) (reste de série s2))};;

let rec multsérie par constante c s =

 

{Constante = c * s.Constante; Reste = Gelé

(function () -> multsérie par constante c (reste de série s))};;

 

let rec multsérie s1 s2 =

 

{Constante = s1.Constante * s2.Constante;

Reste =

Gelé

(function () -> addsérie (mult série par constante s1.Constante (reste de série s2))

 

(mult série (reste de série s1) s2))};;

let opposée de série s = mult série par constante moinsun s;;

 

L’intégration des séries ne pose pas plus de problèmes:

let rec integresérie c0 s =

 

{Constante = c0;

Reste = Gelé (function () -> integredepuis un s)}

 

and integredepuis n s =

 

{Constante = s.Constante / n;

Reste = Gelé (function () -> integredepuis (n + un) (reste de série s))};;

 

Un petit utilitaire d’impression (na¨?ve) des séries entières:

let printvariable = function

 

0 -> false

| 1 -> print string "z"; true

| n -> print string "z^"; printint n; true;; let print terme plus degré s = let c = s.Constante in if c = zéro then false else if c = un then begin printstring plus; printvariable degré end else if c = moins un

then begin print string "- "; printvariable degré end else

begin

if c >= zéro then printstring plus else printstring "- "; printnum (absnum c); printvariable degré

end;;

let printfirstterme s =

 

let c = s.Constante in

if c = zéro then false else begin printnum c; true end;;

 

De même que pour les listes paresseux, notre imprimeur nécessite une limite qui arrête l’impression au bout d’un certain nombre de termes.

let rec printsérie until s =

 

openhovbox 1; let c = s.Constante in if until == 0 then printnum c else let rest = ref s in

let zéro = not (print first terme !rest) in if not zéro then print space(); for i = 1 to until do

rest := reste de série !rest; let delim = if i == 1 & zéro then "" else "+ " in if printterme delim i !rest then printspace()

 

done; printstring "+ O(z^"; printint (succ until);

 

printstring ")"; closebox();;

Nous pouvons maintenant définir (récursivement) les séries entières des fonctions sinus et cosinus:

let rec sinus =

{Constante = zéro;

Reste = Gelé (function () -> integredepuis un cosinus)} and cosinus =

{Constante = un;

Reste = Gelé (function () -> integredepuis un (opposée de série sinus))};; sinus : série = {Constante=0; Reste=Gelé <fun>} cosinus : série = {Constante=1; Reste=Gelé <fun>}

Et cette définition très na¨?ve est cependant effective:

printsérie 10 sinus;; z - 1/6z^3 + 1/120z^5 - 1/5040z^7 + 1/362880z^9 + O(z^11)- : unit = () printsérie 10 cosinus;;

1 - 1/2z^2 + 1/24z^4 - 1/720z^6 + 1/40320z^8 - 1/3628800z^10 + O(z^11)

Notez une fois de plus la magie de la paresse: les deux séries se développent mutuellement a` la demande.

Un joli théorème permet de deviner facilement la valeur de la série s suivante:

let s = addsérie (multsérie sinus sinus) (multsérie cosinus cosinus);;

 

Si le dernier mot reste évidemment au mathématicien, on est heureux de constater que la machine calcule une approximation sans faille du résultat théorique:

printsérie 10 s;;

 

1 + O(z^11)- : unit = ()

 

Un peu de combinatoire des mots

Mots de Lukasiewicz, nombres de Catalan

Définition et proprie´tés des mots de Lukasiewicz

Les mots de Lukasiewicz sont des mots sur l’alphabet {?1,1}, qu’on notera u = (u0,u1,...,un?1) (n = `(u) est la longueur du mot), et qui vérifient les deux propriétés suivantes:

2;

On note ici M (resp. L) l’ensemble des mots sur {?1,1} (resp. l’ensemble des mots de Lukasiewicz).

Notons que ?1 est l’unique mot de Lukasiewicz de longueur 1, qu’il n’y en a pas de longueur 2, et que (1,?1,?1) est l’unique mot de Lukasiewicz de longueur

3.

On appellera capsule d’un mot u ? M un sous-mot de la forme (+1)(?1)(?1). On définit un décapsuleur :

si u ne contient pas de capsule;

,     si (ui,ui+1,ui+2) = (+1,1) est la première capsule de

Comme `(?(u)) ? `(u), on peut définir ?? qui associe a` un mot u la limite de la suite (?n(u)).

On démontre alors de fac¸on élémentaire que l’on a l’équivalence:

?u ? M,u ? L ?? ??(u) = (?1).

En outre on peut prouver que si u et v sont des mots de Lukasiewicz, alors (1) ] u ] v est un mot de Lukasiewicz ( ] dénote ici l’opérateur de concaténation des mots). Mieux, on a la décomposition inverse: tout mot de Lukasiewicz de longueur au moins égale à 3 est de la forme (1) ] u ] v ou` u et v sont de

Lukasiewicz.

C’est ce qui fait penser à imaginer une bijection ? de L sur l’ensemble B des arbres binaires (définis en Caml par type arbre = Vide | Nœud(arbre,arbre)), et qu’on définit ainsi:



                   ?(Vide ) = (?1),             et            ?(Nœud(g,d) ) = (1) ] ?(g) ] ?(d).

On vérifie que ? est bien bijective.

On trouvera dans les programmes 1 et 2 suivants, pages 10 et 11, les fonctions Caml correspondant a` cette étude.

Nombres de Catalan

On note ici an le nombre de mots de Lukasiewicz de longueur n. On a donc a0 = 0, a1 = 1, a2 = 0, a3 = 1, et on traduit la décomposition décrite ci-dessus des mots de Lukasiewicz par la relation de récurrence:

                                                             ?n ? 3,an =              X aiaj.

i+j=n?1

Soit  la série génératrice correspondante. Les relations précédentes se traduisent par:

                                                     2            +?                                          n             +?                     n

                                                     S(z) = X( X aiaj)z                  = X an+1z ,

                                                                 n=0 i+j=n                                       n=2

donc S(z) = z + zS(z)2.

Programme 1 Les mots de Lukasiewicz

? exception Not Lukasiewicz ;;

?

? let rec somme m k =

        ?               if k = 0 then 0

        ?                     else (hd m) + somme (tl m) (k - 1) ;;

?

? let rec rho = function

        ?                           | 1 :: -1 :: -1 :: reste -> true, -1 :: reste

        ?                             | x :: reste -> let flag, m’ = rho reste in flag, x::m’

      ??               | m -> false, m ;;

??

?? let rec rho étoile m =

      ??            match rho m with

      ??                       | false, m’ -> m’

      ??                            | true, m’ -> rho étoile m’ ;;

??

?? let est Lukasiewicz m =

      ??              match rho étoile m with

      ??                       | [-1] -> true

      ??                         | -> false ;;

??

?? let rec décompose suffixe =

      ??               let rec décomprec m s =

      ??                    match m with

      ??                               | n :: m’ ->                     if n + s = -1 then [n] , m’

      ??                                                             else                 let g,d = décomprec m’ (n + s)

      ??                                                                              in

      ??                                                                                 n :: g , d

      ??                                    | -> raise NotLukasiewicz

      ??           in

      ??               décomp rec suffixe 0 ;;

??

?? type arbre = Feuille | Nœud of arbre * arbre ;;

??

?? let rec Lukasiewicz of arbre = function

      ??                | Feuille -> [-1]

      ??           | Nœud(g,d)

      ??                                      -> 1 :: (Lukasiewicz of arbre g) @ (Lukasiewicz of arbre d) ;;

??

?? let rec arbre of Lukasiewicz = function

      ??                | [-1] -> Feuille

      ??                      | 1 :: reste -> let gauche,droit = décompose reste

      ??                                            in

      ??                                                  Nœud((arbre of Lukasiewicz gauche),

      ??                                                              (arbre of Lukasiewicz droit))

??

Programme 2 Dessin d’arbres et mots de Lukasiewicz

?? #open "graphics" ;; ??

?? opengraph "" ;;

??

?? let rec profondeurarbre = function

??               | Feuille -> -1

??                         | Nœud(g,d) -> 1 + max (profondeur arbre g) (profondeur arbre d) ;;

??

?? let profondeurLukasiewicz m = profondeur arbre (arbre of Lukasiewicz m) ;; ??

?? let rotation (x,y) = (y-x+240,276-x-y) ;;

??

?? let point x y = let x’,y’ = rotation(x,y) in fillcircle x’ y’ 2 ;;

?? let va à x y = let x’,y’ = rotation(x,y) in moveto x’ y’ ;;

?? let tracer x y = let x’,y’ = rotation(x,y) in lineto x’ y’ ;;

??

?? let rec deuxpuissance = function

??            | 0 -> 1

??                   | n -> let x = deuxpuissance (n/2)

??                         in

??                                      if n mod 2 = 0 then x * x else 2 * x * x ;;

??

?? let dessine mot =

??                  let rec dessinrec a x0 y0 =

??                      point x0 y0 ;

??                    match a with

??                                | Feuille -> ()

??                            | Nœud(g,d)

??                                     -> let delta =

??                                                           3 * (deuxpuissance (profondeurarbre a))

??                                        in

??                                        begin

??                                                        dessin rec g (x0 + delta) y0 ;

??                                                        dessin rec d x0 (y0 + delta) ;

??           va à (x0 + delta) y0 ; ??        tracer x0 y0 ;

??                                                     tracer x0 (y0 + delta)

??                                       end

??          in

??                     dessin rec (arbre of Lukasiewicz mot) 0 0 ;;

 

On résout (comme on le fait d’habitude avec les séries génératrices), et on obtient

.

Or on a classiquement:

,

et on en déduit le développement de S(z):

                                       ,                                                                                 et .

Ces nombres ont été baptisés nombres de Catalan.

Mots de Lyndon, ordre lexicographique

On considère cette fois les mots sur l’alphabet {0,1}. Leur ensemble sera noté ici M. On définit classiquement l’ordre lexicographique sur l’ensemble M. Il s’agit d’un ordre total sur M, que nous noterons ici ¹.

Siu par rotation:u = (u0,u1,...,uu?(kn)?1=) u? M?(k0), on noteradès que k ?u?(kk0) [le mot obtenu à partir den] et, si 0 ? k ? n ? 1,

u?(k) = (                1). Un motk on a u ¹ u?(k).

On démontre alors que tout mot de Lyndon u de longueur au moins égale à 2 s’écrit sous la forme u = u1 ] u2 ou` u1 et u2 sont deux mots de Lyndon tels que u1 ¹ u2. Réciproquement, si u1 et u2 sont deux mots de Lyndon tels que u1 ¹ u2, alors u1 ] u2 est effectivement un mot de Lyndon.

On peut aussi définir ce qu’on appelle une factorisation de Lyndon d’un mot u quelconque: il s’agit d’une décomposition u = u0 ] u1 ] ··· ] uk, ou` chacun des ui est un mot de Lyndon et ou` de plus uk ¹ uk?1 ¹ ··· ¹ u1 ¹ u0.

Un algorithme de décomposition est le suivant:

1.    on part de la décomposition u = (u0) ] (u1) ] ··· ] (un?1) en mots de longueur 1;

2.    on cherche dans la décomposition courante u = u0 ] u1 ] ··· ] uk s’il existe un indice j tel que uj ¹ uj+1. Si oui, on passe a` 3, sinon on a terminé;

3.    on remplace la décomposition u = u0 ] u1 ] ··· ] uk par la décomposition u = v0 ] v1 ] ··· ] vk?1 ou` vi = ui si i < j, vj = uj ] uj+1, et vi = ui+1 si i > j, et on retourne a` 2.

Par exemple, la décomposition de Lyndon du mot (0101001100100) est (01)(01)(0011)(001)(0)(0).

   

?

? type comparaison = Inférieur | Egal | Sup´                     érieur ;;

?

? let rec ordre u v = match u,v with

?                 | [],[] -> Egal´

?           | [], -> Inférieur | ,[] -> Supérieur

?                    | u0 :: u’ , v0 :: v’

??                           -> if u0 = v0 then ordre u’ v’

??                                     else if u0 < v0 then Inférieur else Supérieur ;;

??

?? let rec estpréfixe a mot = match a with

??              | [] -> true

??                 | a0 :: a’ -> match mot with

??                                                     | m0 :: m’ when a0 = m0 -> estpréfixe a’ m’

??                                                  |  -> false ;;

??

?? let estsuffixe a mot =

??                  let rec shift l = function

??                     | 0 -> l

??                             | n -> shift (tl l) (n - 1)

??          in

??                         let la,lm = (listlength a),(listlength mot)

??          in

??                if la > lm then false

??                     else a = (shift mot (lm - la)) ;;

??

?? let rotation mot = (tl mot) @ [ hd mot ] ;;

??

?? let est Lyndon def mot =

??                let n = list length mot

??            and m = ref mot

??          in

??           try

??                        for i = 1 to n do

??                               m := rotation! m ;

??                                      if (ordre mot! m) = Supérieur then raise NotLyndon

??                   done ;

??                   true

??                with Not Lyndon -> false ;;

??

?? let est Lyndon mot =

??                let rec test = function

??                      | [] -> true

??                                  | (a :: q) as m’ -> (Inférieur = ordre mot m’) && (test q)

??          in

??               test (tl mot) ;;

 

Programme 4 Factorisation des mots de Lyndon

?? let factorisation de Lyndon mot =

      ??                let rec réduit = function

      ??                           | (a :: b :: q) as ll

      ??                                      -> ( if (ordre a b) = Inférieur then

      ??                                                                let m, = réduit ((a @ b) :: q) in m,true

      ??                                        else

      ??                                                          match réduit (b :: q) with

      ??                                                                   | m,true -> réduit (a :: m)



      ??                                                                   | m,false -> ll,false                                                        )

      ??                         | ll -> ll,false

      ??           in

      ??                            match réduit (map (function x -> [x]) mot) with ll, -> ll ;;

??

?? let Lyndon =

      ??                   let rec insertion x = function

      ??                       | [] -> [x]

      ??                           | y :: q -> match ordre x y with

      ??                                                             | Inférieur -> x :: y :: q

      ??                                                         | Egal -> y :: q´

      ??                                                              | Supérieur -> y :: (insertion x q)

      ??           in

      ??                   let rec mapaccu f accu = function

      ??                      | [] -> accu

      ??                           | x :: q -> match f(x) with

      ??                                                           | [] -> mapaccu f accu q

      ??                                                               | y -> mapaccu f (insertion y accu) q

      ??           in

      ??                let compose un x1 l2 accu =

      ??                               map accu (function x2 -> if Inférieur = ordre x1 x2

      ??                                                                            then x1 @ x2 else [])

      ??                                       accu l2

      ??           in

      ??                 let rec compose l1 l2 accu =

      ??                     match l1 with

      ??                               | [] -> accu

      ??                                       | x1 :: q -> compose q l2 (composeun x1 l2 accu)

      ??           in

      ??                  let rec composetout f n k accu =

      ??                                     if k < n then composetout f n (k+1) (compose (f k) (f (n-k)) accu)

      ??                    else accu

      ??           in

      ??                           let mémoire = ref [ (0,[]) ; (1,[ [0] ; [1] ]) ]

??           in ??       let rec f n =

      ??                      try assoc n! mémoire

      ??                                with Notfound -> let res = composetout f n 1 []

      ??                                                         in

      ??                                                              mémoire := (n,res) ::! mémoire ;

      ??                                                         res

      ??           in

      ??            f ;;

 

Permutations

La représentation choisie ici

Une idée naturelle pour définir une permutation suit la définition mathématique: une permutation est une application ? de {1,...,n} dans lui-même. Un type Caml adapté est donc

type permutation = int * (int -> int) ;;

dans la mesure ou` on définira une permutation comme le couple (n,?).

En écrivant sur cette base la fonction qui a` ? associe ??1, sa réciproque, je me suis aperc¸u que j’étais conduit a` passer par l’intermédiaire de la représentation vectorielle des permutations: peut-être y a-t-il une solution élégante, qui reste dans l’esprit de la représentation fonctionnelle des permutations, mais je ne l’ai pas trouvée.

On choisit donc ici de représenter une permutation de {1,...,n} par un vecteur d’entiers: la permutation ? est représentée par le vecteur d’entiers

v(?) = [| ?(1);?(2);...;?(n) |].

On n’aura pas oublié que Caml indexe les vecteurs à partir de 0. Ainsi donc on récupérera ?(i) en évaluant v.(i?1). Cela justifie les deux fonctions fondamentales suivantes:

let image v k = v.(k - 1) and affecte v k x = v.(k-1) <- x ;;

De cette fa¸con, on écrira par exemple ainsi la permutation identique:

let identité n = let v = makevect n 1 in

for i = 1 to n do affecte v i i done ; v ;;

Quelques fonctions simples

Voici tout d’abord de quoi vérifier qu’un vecteur d’entiers donné représente bien une permutation:

let rec intervalled’entiers i j = if i > j then []

else i :: (intervalled’entiers (i+1) j) ;;

let estpermutation v = let n = vect length v in

let un a n = intervalled’entiers 1 n

in

let rec est ok = function

| [] -> true

| a :: q -> (not (mem a q)) && (mem a un a n) && (estok q) in

estok (list of vect v) ;;

On pourra reprocher a` cette version d’être quadratique. Une version linéaire est par exemple la suivante:

let estpermutation v = let n = vect length v in

let test = make vect n false

in

try for i = 0 to (n-1) do let j = v.(i) - 1 in if test.(j) then failwith "doublon"

else test.(j) <- true

done ; true

with  -> false ;;

On observera que le filtrage d’exception try ... with-> false permet non seulement de rattraper l’erreur Failure "doublon" mais aussi les erreurs que déclencherait l’appel a` test.(j) dans le cas ou` le vecteur de taille n contiendrait un élément supérieur a` n.

On écrit ensuite naturellement la composition des permutations:

let compose v v’ = let n,n’ = (vectlength v),(vectlength v’) in

if n = n’ then let w = makevect n 1

in

for i = 1 to n do affecte w i (image v (image v’ i)) done ; w

else failwith "Composition de deux permutations de tailles différentes" ;;

L’orbite d’un entier k pour la permutation ? est l’ensemble {?j(k),j ? N}. On l’obtient facilement ainsi:

let orbite v k = let rec augmenteorbite k liste = if mem (image v k) liste then liste else augmenteorbite (image v k) ((image v k) :: liste) in

augmenteorbite k [ k ] ;;

Pour rechercher les points fixes d’une permutations, il paraˆ?t naturel d’écrire la fonction que j’ai baptisée select (et qui me semble manquer a` la bibliothèque standard de Caml) qu’on peut définir ainsi:

let rec select prédicat = function

| [] -> []

| a :: q -> if (prédicat a) then a :: (select prédicat q)

else (select prédicat q) ;;

et qui choisit ceux des éléments d’une liste qui vérifient un prédicat (id est une fonction de type ’a -> bool) donné.

On a alors tout simplement:

let points fixes v = let n = vect length v in

select (function x -> x = (image v x)) (intervalleentier 1 n) ;;

Notre choix d’une représentation vectorielle des permutations rend élémentaire l’écriture de la réciproque:

let réciproque v = let n = vectlength v in

let w = makevect n 1

in

for i = 1 to n do affecte w (image v i) i done ; w ;;

Pour terminer dans cette petite collection, je vous propose maintenant de décomposer une permutation en cycles:

let rec ^ote x = function

| [] -> []

| a :: q when a = x -> q

| a :: q -> a :: (^ote x q) ;;

fait comme la fonction subtract de la bibliothèque standard de Caml, mais ne supprime d’une liste que la première occurrence d’un objet x donné, ce qui suffit dans le cas des permutations.

On est en mesure de construire la décomposition en cycles (on renvoie la liste des cycles, eux-mêmes représentés par des listes):

let cycles v = let rec uncycle x0 x candidats = if (image v x) = x0 then [ x0 ] , (^ote x candidats) else let queue,c’ = uncycle x0 (image v x) (^ote x candidats) in x :: queue,c’

in let rec épuise = function

| [] -> []

                                        | a ::  as liste ->                             let cycle,candidats = uncycle a a liste

in

cycle :: (épuise candidats)

in

épuise (list of vect v) ;;

Le problème de la génération des permutations

Ge´nération re´cursive de l’ensemble des permutations

let échange v i j = let x = v.(i)

in

v.(i) <- v.(j) ;

v.(j) <- x ;;

permet bien entendu d’échanger deux éléments d’un vecteur.

On écrit maintenant l’analogue d’un do list f Sn : étant donnés une fonction f : int -> unit et un entier n, do list f n applique la fonction a` toutes les permutations de {1,...,n} tour a` tour. La fonction construit récursivement — par échanges successifs — les permutations à partir de la permutation identique. C’est permrec qui fait tout le travail, en échangeant tour a` tour l’élément i avec tous les suivants. Quand elle est appelée avec i = n ? 1 c’est qu’on a une permutation toute prête, qu’on passe alors a` la fonction f.

let applique aux permutations f n = let v = vect of list (intervalled’entiers 1 n) in

let rec perm rec i =

if i = n - 1 then f v

else

for j = i to n - 1 do

échange v i j ; permrec (i+1) ;

échange v i j done

in

permrec 0 ;;

On vérifie que chaque permutation est engendrée une fois et une seule: cette fonction a une complexité O(n!).

Application: on souhaite imprimer la liste complète de toutes les permutations de {1,2,...,n} pour un n fixé; on commencera par définir une fonction d’impression d’une permutation, comme celle-ci (qui est évidemment très rudimentaire):

let print permutation v = for i = 0 to (vectlength v) - 1 do print int v.(i) ; print char ‘ ‘

done ; print newline () ;;

L’invocation suivante permet alors d’imprimer tour a` tour toutes les permutations:

let toutes les permutations = applique aux permutations printpermutation ;;

Une méthode tout à fait différente

Remarquant que l’on peut définir un ordre sur Sn en rangeant les permutations dans l’ordre lexicographique, on souhaite écrire une fonction qui calcule la permutation qui succède à une permutation donnée, ou qui déclenche une exception dans le cas ou` la permutation fournie est la dernière (c’est-à-dire en l’occurrence la permutation (n,n ? 1,...,3,2,1)).

Expliquons sur un exemple l’algorithme utilisé. Soit ? = (346521) une permutation élément de S6, la suivante est ?0 = (351246). Comment la calculer. On recherche tout d’abord le plus grand suffixe décroissant de ? : c’est ici (6521). La fonction débutsuffixe ci-dessous renvoie donc 1, l’indice de 4, qui précède le suffixe. C’est elle qui sait déclencher l’exception No more permutation qui signale qu’on a fourni la dernière permutation de Sn, qu’elle reconnaˆ?t facilement.

On retourne alors le suffixe, obtenant dans notre exemple la permutation (341256). Il suffit pour terminer d’échanger le 4 qui balisait le début du préfixe avec le premier (de gauche a` droite) élément du suffixe qui lui est supérieur (ici il s’agit de 5): on obtient bien ?0 = (351246). exception No more permutation ;;

let permutation suivante v = let n = vect length v

in let rec début suffixe i = if i <= 0 then raise No more permutation else if v.(i) < v.(i-1) then début suffixe (i-1) else i-1

and retournesuffixe a b = if a < b then

begin

échange v a b ; retournesuffixe (a + 1) (b - 1)

end

and place k j = if v.(j) > v.(k) then échange v j k else place k (j + 1)

and modifie suffixe k = retourne suffixe (k + 1) (n - 1) ; place k (k + 1)

in modifiesuffixe ( débutsuffixe (n - 1) ) ;;



126