Sys.command "ocaml -version";;
The OCaml toplevel, version 4.04.2
- : int = 0
Merci à Pierre et Clarence, élèves de la préparation à l'agrégation en 2018/2019, de m'avoir autorisé à utiliser une partie de leur implémentation pour cette (proposition de) correction.
La question de programmation pour ce texte était donnée en page 5, et était assez courte :
"Implanter dans l’un des langages de programmation autorisés l’algorithme de test de permutation."
Dans l'ordre, on va :
"5340"
en un mot [|5;4;3;0|]
,[|1;0;2;3|]
,En bonus, on implémente aussi le test de moyenne, et on illustre le bon fonctionnement de notre implémentation sur les exemples du texte.
On travaille avec des mots représentés comme des tableaux d'entiers.
type mot = int array ;;
type mot = int array
On présente deux implémentations, la première n'est pas très réfléchie et se trouve être avoir une complexité temporelle en $\mathcal{O}(|mot|^2)$, tandis que la seconde est plus réfléchie et fonctionne en temps linéaire $\mathcal{O}(|mot|)$.
On va supposer que chaque valeur du mot d'entrée est bien dans $\{0,\dots,n-1\}$, et on vérifie simplement que chaque valeur est présente une et une seule fois (si $n=|mot|$).
Pour chaque valeur $i\in\{0,\dots,n-1\}$, on parcourt le mot à la recherche d'une valeur $m[j]=i$.
let est_permut (m : mot) : bool =
let p = Array.length m in
let permut_bool = ref true in
let i = ref 0 in
while !i<p && !permut_bool do
permut_bool := !permut_bool && ( Array.exists (fun x -> x = !i) m );
incr i
done;
!permut_bool;;
(* Complexité temporelle au pire en O(p^2) *)
(* Complexité spatiale en O(p) *)
val est_permut : mot -> bool = <fun>
est_permut [|3; 5; 1; 2; 4; 0|];; (* true ! *)
est_permut [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)
- : bool = true
- : bool = false
Au lieu de parcourir les valeurs à trouver et de les chercher, on peut parcourir les valeurs directement !
let est_permut_lineaire (m : mot) : bool =
let p = Array.length m in
let tous_vus = Array.make p false in
Array.iter (fun mi ->
tous_vus.(mi) <- true
) m;
Array.for_all (fun b -> b) tous_vus
;;
(* Complexité temporelle au pire en O(p) *)
(* Complexité spatiale en O(p) *)
val est_permut_lineaire : mot -> bool = <fun>
est_permut_lineaire [|3; 5; 1; 2; 4; 0|];; (* true ! *)
est_permut_lineaire [|3; 5; 1; 3; 4; 0|];; (* false ! il manque le 2, il y a deux fois le 3 *)
- : bool = true
- : bool = false
On va faire quelques mesures empiriques du temps de calcul, entre la fonction linéaire et la fonction quadratique.
Cela illustre aussi l'utilisation de Sys.time()
pour obtenir le temps système.
let echange t i j =
let tmp = t.(i) in
t.(i) <- t.(j);
t.(j) <- tmp;
;;
val echange : 'a array -> int -> int -> unit = <fun>
Random.self_init ();;
- : unit = ()
On génère une permutation aléatoire facilement, en faisant plein d'échanges aléatoires (nombre et localisation aléatoires). Attention, on essaie pas de generer selon la loi uniforme dans $\Sigma_p$, c'est beaucoup plus difficile !
let permutation_aleatoire p =
let m = Array.init p (fun i -> i) in
for _ = 1 to Random.int (10*p) do
echange m (Random.int p) (Random.int p);
done;
m
;;
val permutation_aleatoire : int -> int array = <fun>
permutation_aleatoire 10;;
- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]
permutation_aleatoire 10;;
- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]
permutation_aleatoire 10;;
- : int array = [|1; 3; 7; 9; 8; 4; 5; 0; 2; 6|]
Cette petite fonction permet de mesurer le temps machine mis pour calculer une fonction f ()
:
let timeit f () =
let debut = Sys.time () in
let res = f () in
let fin = Sys.time () in
Printf.printf "\nTemps pour calculer f() = %f seconde(s)." (fin -. debut);
res
;;
val timeit : (unit -> 'a) -> unit -> 'a = <fun>
On va s'en servir avec cette fonction, qui test nombre_test
fois la vérification f_est_permut
sur une permutation aléatoire de taille taille
.
let test f_est_permut nombre_test taille () =
Printf.printf "\nDébut de %i tests de taille %i..." nombre_test taille;
flush_all ();
for _ = 1 to nombre_test do
let m = permutation_aleatoire taille in
assert (f_est_permut m);
done
;;
val test : (int array -> bool) -> int -> int -> unit -> unit = <fun>
timeit (test est_permut_lineaire 100 1000) ();;
timeit (test est_permut_lineaire 100 2000) ();;
timeit (test est_permut_lineaire 100 4000) ();;
Printf.printf "\n\n\n";;
flush_all();;
- : unit = ()
Début de 100 tests de taille 1000... Temps pour calculer f() = 0.211866 seconde(s).
- : unit = ()
Début de 100 tests de taille 2000... Temps pour calculer f() = 0.316790 seconde(s).
- : unit = ()
- : unit = ()
Début de 100 tests de taille 4000... Temps pour calculer f() = 0.574821 seconde(s).
- : unit = ()
timeit (test est_permut 100 1000) ();;
timeit (test est_permut 100 2000) ();;
timeit (test est_permut 100 4000) ();;
Printf.printf "\n\n\n";;
flush_all();;
- : unit = ()
Début de 100 tests de taille 1000... Temps pour calculer f() = 1.389953 seconde(s).
- : unit = ()
Début de 100 tests de taille 2000... Temps pour calculer f() = 5.122529 seconde(s).
- : unit = ()
- : unit = ()
Début de 100 tests de taille 4000... Temps pour calculer f() = 20.058526 seconde(s).
- : unit = ()
On peut afficher ces trois valeurs, juste pour mieux les visualiser :
let trouve_omega (m : mot) : mot =
let p = Array.length m in
let omega = Array.make p 0 in
for i=0 to (p-1) do
omega.(i) <- (i + m.(i)) mod p
done;
omega;;
val trouve_omega : mot -> mot = <fun>
trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;
- : mot = [|1; 2; 0|]
- : mot = [|1; 0; 2; 3|]
Note : on peut être plus rapide avec une fonction Array.init
au lieu de Array.make
:
Array.make;;
Array.init;;
- : int -> 'a -> 'a array = <fun>
- : int -> (int -> 'a) -> 'a array = <fun>
let trouve_omega (m : mot) : mot =
let p = Array.length m in
Array.init p (fun i -> ((i + m.(i)) mod p))
;;
val trouve_omega : mot -> mot = <fun>
trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;
- : mot = [|1; 2; 0|]
- : mot = [|1; 0; 2; 3|]
mot
¶On a d'abord besoin de convertir un caractère comme '5'
en un entier 5
.
Cela peut se faire manuellement comme ça :
let entier (s : char) : int = match s with
| '0'-> 0
| '1'-> 1
| '2'-> 2
| '3'-> 3
| '4'-> 4
| '5'-> 5
| '6'-> 6
| '7'-> 7
| '8'-> 8
| '9'-> 9
;;
File "[41]", line 1, characters 30-162: Warning 8: this pattern-matching is not exhaustive. Here is an example of a case that is not matched: 'a'
val entier : char -> int = <fun>
let entier (s : char) : int =
(int_of_char s) - (int_of_char '0')
;;
val entier : char -> int = <fun>
Pour la transformation de la chaîne en un mot, on peut le faire manuellement comme ça :
let transfo_mot (m : string) : mot =
let p = String.length m in
let mot_tableau = Array.make p 0 in
for i = 0 to (p - 1) do
mot_tableau.(i) <- entier (m.[i])
done;
mot_tableau;;
(* Complexité temporelle et spatiale en O(p) *)
val transfo_mot : string -> mot = <fun>
transfo_mot "5241";;
- : mot = [|5; 2; 4; 1|]
Mais on peut aussi accélérer un peu :
Array.init
- : int -> (int -> 'a) -> 'a array = <fun>
let transfo_mot (m : string) : mot =
Array.init (String.length m) (fun i -> (entier m.[i]))
(* Complexité temporelle et spatiale en O(p) *)
val transfo_mot : string -> mot = <fun>
transfo_mot "5241";;
- : mot = [|5; 2; 4; 1|]
let test_permut (m : string) : bool =
est_permut (trouve_omega (transfo_mot m));;
(* Complexité temporelle en O(p) *)
val test_permut : string -> bool = <fun>
let test_permut_mot (m : mot) : bool =
est_permut (trouve_omega m);;
(* Complexité temporelle en O(p) *)
val test_permut_mot : mot -> bool = <fun>
Quelques exemples :
test_permut "433";; (* pas jonglable *)
- : bool = false
test_permut "432";; (* pas jonglable *)
- : bool = false
test_permut "441";; (* jonglable *)
- : bool = true
test_permut "5241";; (* jonglable *)
- : bool = true
test_permut "9340";; (* jonglable *)
- : bool = true
Cet autre test n'est pas une condition nécessaire et suffisante, mais il est rapide à implémenter :
let test_moyenne_mot (m : mot) (b : int) : bool =
let p = Array.length m in
let s = ref 0 in
for i = 0 to (p - 1) do
s:= !s + m.(i)
done;
!s / p = b (* on teste l'égalité *)
;;
val test_moyenne_mot : mot -> int -> bool = <fun>
test_moyenne_mot [|5;4;3;0|] 3;;
- : bool = true
On va finir par quelques exemples :
let test_moyenne (m : string) (b : int) : bool =
test_moyenne_mot (transfo_mot m) b;;
val test_moyenne : string -> int -> bool = <fun>
test_moyenne "433" 3;;
- : bool = true
test_moyenne "443" 3;;
- : bool = true
test_moyenne "432" 3;;
- : bool = true
test_moyenne "5430" 3;;
- : bool = true
La fonction suivante donne la liste des mots de taille p
commençant par debut
(dont la somme des coefficients vaut somme
) concaténée avec acc
, en temps $\mathcal{O}(m^p)$.
let rec partition_aux balles p debut somme acc =
let m = balles * p in
let manque = Array.fold_left (fun c x -> if x = (-1) then c + 1 else c) 0 debut in
if manque = 1 then
let t = Array.copy debut in
t.(p - 1) <- m - somme;
t :: acc
else
let nacc = ref acc in
for k = m - somme downto 0 do
let ndebut = Array.copy debut in
ndebut.(p - manque) <- k;
nacc := partition_aux balles p ndebut (somme + k) !nacc
done;
!nacc
;;
val partition_aux : int -> int -> int array -> int -> int array list -> int array list = <fun>
let partition balles p =
let debut = Array.make p (-1) in
partition_aux balles p debut 0 []
;;
val partition : int -> int -> int array list = <fun>
let bp balles p = List.filter test_permut_mot (partition balles p);;
val bp : int -> int -> mot list = <fun>
Par exemples :
partition 3 3;;
- : int array list = [[|0; 0; 9|]; [|0; 1; 8|]; [|0; 2; 7|]; [|0; 3; 6|]; [|0; 4; 5|]; [|0; 5; 4|]; [|0; 6; 3|]; [|0; 7; 2|]; [|0; 8; 1|]; [|0; 9; 0|]; [|1; 0; 8|]; [|1; 1; 7|]; [|1; 2; 6|]; [|1; 3; 5|]; [|1; 4; 4|]; [|1; 5; 3|]; [|1; 6; 2|]; [|1; 7; 1|]; [|1; 8; 0|]; [|2; 0; 7|]; [|2; 1; 6|]; [|2; 2; 5|]; [|2; 3; 4|]; [|2; 4; 3|]; [|2; 5; 2|]; [|2; 6; 1|]; [|2; 7; 0|]; [|3; 0; 6|]; [|3; 1; 5|]; [|3; 2; 4|]; [|3; 3; 3|]; [|3; 4; 2|]; [|3; 5; 1|]; [|3; 6; 0|]; [|4; 0; 5|]; [|4; 1; 4|]; [|4; 2; 3|]; [|4; 3; 2|]; [|4; 4; 1|]; [|4; 5; 0|]; [|5; 0; 4|]; [|5; 1; 3|]; [|5; 2; 2|]; [|5; 3; 1|]; [|5; 4; 0|]; [|6; 0; 3|]; [|6; 1; 2|]; [|6; 2; 1|]; [|6; 3; 0|]; [|7; 0; 2|]; [|7; 1; 1|]; [|7; 2; 0|]; [|8; 0; 1|]; [|8; 1; 0|]; [|9; 0; 0|]]
bp 3 3;;
- : mot list = [[|0; 0; 9|]; [|0; 1; 8|]; [|0; 3; 6|]; [|0; 4; 5|]; [|0; 6; 3|]; [|0; 7; 2|]; [|0; 9; 0|]; [|1; 1; 7|]; [|1; 2; 6|]; [|1; 4; 4|]; [|1; 5; 3|]; [|1; 7; 1|]; [|1; 8; 0|]; [|2; 0; 7|]; [|2; 2; 5|]; [|2; 3; 4|]; [|2; 5; 2|]; [|2; 6; 1|]; [|3; 0; 6|]; [|3; 1; 5|]; [|3; 3; 3|]; [|3; 4; 2|]; [|3; 6; 0|]; [|4; 1; 4|]; [|4; 2; 3|]; [|4; 4; 1|]; [|4; 5; 0|]; [|5; 0; 4|]; [|5; 2; 2|]; [|5; 3; 1|]; [|6; 0; 3|]; [|6; 1; 2|]; [|6; 3; 0|]; [|7; 1; 1|]; [|7; 2; 0|]; [|8; 0; 1|]; [|9; 0; 0|]]
On voit que l'on retrouve les mots donnés en exemples dans le texte, 441, 423, 333 par exemple :
List.mem [|4; 4; 1|] (bp 3 3);;
List.mem [|4; 2; 3|] (bp 3 3);;
List.mem [|3; 3; 3|] (bp 3 3);;
- : bool = true
- : bool = true
- : bool = true
Et le mot 433 n'est pas dans la liste calculée :
List.mem [|4; 3; 3|] (bp 3 3);;
- : bool = false
Pour $m=4$, on commence à avoir beaucoup plus de réponses :
partition 4 4;;
List.length (partition 4 4);;
- : int array list = [[|0; 0; 0; 16|]; [|0; 0; 1; 15|]; [|0; 0; 2; 14|]; [|0; 0; 3; 13|]; [|0; 0; 4; 12|]; [|0; 0; 5; 11|]; [|0; 0; 6; 10|]; [|0; 0; 7; 9|]; [|0; 0; 8; 8|]; [|0; 0; 9; 7|]; [|0; 0; 10; 6|]; [|0; 0; 11; 5|]; [|0; 0; 12; 4|]; [|0; 0; 13; 3|]; [|0; 0; 14; 2|]; [|0; 0; 15; 1|]; [|0; 0; 16; 0|]; [|0; 1; 0; 15|]; [|0; 1; 1; 14|]; [|0; 1; 2; 13|]; [|0; 1; 3; 12|]; [|0; 1; 4; 11|]; [|0; 1; 5; 10|]; [|0; 1; 6; 9|]; [|0; 1; 7; 8|]; [|0; 1; 8; 7|]; [|0; 1; 9; 6|]; [|0; 1; 10; 5|]; [|0; 1; 11; 4|]; [|0; 1; 12; 3|]; [|0; 1; 13; 2|]; [|0; 1; 14; 1|]; [|0; 1; 15; 0|]; [|0; 2; 0; 14|]; [|0; 2; 1; 13|]; [|0; 2; 2; 12|]; [|0; 2; 3; 11|]; [|0; 2; 4; 10|]; [|0; 2; 5; 9|]; [|0; 2; 6; 8|]; [|0; 2; 7; 7|]; [|0; 2; 8; 6|]; [|0; 2; 9; 5|]; [|0; 2; 10; 4|]; [|0; 2; 11; 3|]; [|0; 2; 12; 2|]; [|0; 2; 13; 1|]; [|0; 2; 14; 0|]; [|0; 3; 0; 13|]; [|0; 3; 1; 12|]; [|0; 3; 2; 11|]; [|0; 3; 3; 10|]; [|0; 3; 4; 9|]; [|0; 3; 5; 8|]; [|0; 3; 6; 7|]; [|0; 3; 7; 6|]; [|0; 3; 8; 5|]; [|0; 3; 9; 4|]; [|0; 3; 10; 3|]; [|0; 3; 11; ...|]; ...]
- : int = 969
bp 4 4;;
List.length (bp 4 4);;
- : mot list = [[|0; 0; 0; 16|]; [|0; 0; 1; 15|]; [|0; 0; 4; 12|]; [|0; 0; 5; 11|]; [|0; 0; 8; 8|]; [|0; 0; 9; 7|]; [|0; 0; 12; 4|]; [|0; 0; 13; 3|]; [|0; 0; 16; 0|]; [|0; 1; 1; 14|]; [|0; 1; 3; 12|]; [|0; 1; 5; 10|]; [|0; 1; 7; 8|]; [|0; 1; 9; 6|]; [|0; 1; 11; 4|]; [|0; 1; 13; 2|]; [|0; 1; 15; 0|]; [|0; 2; 0; 14|]; [|0; 2; 3; 11|]; [|0; 2; 4; 10|]; [|0; 2; 7; 7|]; [|0; 2; 8; 6|]; [|0; 2; 11; 3|]; [|0; 2; 12; 2|]; [|0; 4; 0; 12|]; [|0; 4; 1; 11|]; [|0; 4; 4; 8|]; [|0; 4; 5; 7|]; [|0; 4; 8; 4|]; [|0; 4; 9; 3|]; [|0; 4; 12; 0|]; [|0; 5; 1; 10|]; [|0; 5; 3; 8|]; [|0; 5; 5; 6|]; [|0; 5; 7; 4|]; [|0; 5; 9; 2|]; [|0; 5; 11; 0|]; [|0; 6; 0; 10|]; [|0; 6; 3; 7|]; [|0; 6; 4; 6|]; [|0; 6; 7; 3|]; [|0; 6; 8; 2|]; [|0; 8; 0; 8|]; [|0; 8; 1; 7|]; [|0; 8; 4; 4|]; [|0; 8; 5; 3|]; [|0; 8; 8; 0|]; [|0; 9; 1; 6|]; [|0; 9; 3; 4|]; [|0; 9; 5; ...|]; ...]
- : int = 369
Voilà pour les deux questions obligatoires de programmation :
Bien-sûr, ce petit notebook ne se prétend pas être une solution optimale, ni exhaustive.