In [1]:
Sys.command "ocaml -version";;
Out[1]:
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.
In [4]:
type mot = int array ;;
Out[4]:
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|$).
In [6]:
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) *)
Out[6]:
In [7]:
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 *)
Out[7]:
Out[7]:
In [8]:
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) *)
Out[8]:
In [9]:
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 *)
Out[9]:
Out[9]:
In [10]:
let echange t i j =
let tmp = t.(i) in
t.(i) <- t.(j);
t.(j) <- tmp;
;;
Out[10]:
In [11]:
Random.self_init ();;
Out[11]:
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 !
In [12]:
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
;;
Out[12]:
In [13]:
permutation_aleatoire 10;;
Out[13]:
In [13]:
permutation_aleatoire 10;;
Out[13]:
In [13]:
permutation_aleatoire 10;;
Out[13]:
Cette petite fonction permet de mesurer le temps machine mis pour calculer une fonction f () :
In [14]:
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
;;
Out[14]:
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.
In [17]:
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
;;
Out[17]:
In [26]:
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();;
Out[26]:
Out[26]:
Out[26]:
Out[26]:
Out[26]:
In [27]:
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();;
Out[27]:
Out[27]:
Out[27]:
Out[27]:
Out[27]:
On peut afficher ces trois valeurs, juste pour mieux les visualiser :
In [37]:
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;;
Out[37]:
In [36]:
trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;
Out[36]:
Out[36]:
Note : on peut être plus rapide avec une fonction Array.init au lieu de Array.make :
In [32]:
Array.make;;
Array.init;;
Out[32]:
Out[32]:
In [38]:
let trouve_omega (m : mot) : mot =
let p = Array.length m in
Array.init p (fun i -> ((i + m.(i)) mod p))
;;
Out[38]:
In [ ]:
trouve_omega [|4;4;1|];;
trouve_omega [|5;3;4;0|];;
Out[ ]:
Out[ ]:
On a d'abord besoin de convertir un caractère comme '5' en un entier 5.
Cela peut se faire manuellement comme ça :
In [ ]:
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
;;
Out[ ]:
In [ ]:
let entier (s : char) : int =
(int_of_char s) - (int_of_char '0')
;;
Out[ ]:
Pour la transformation de la chaîne en un mot, on peut le faire manuellement comme ça :
In [ ]:
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) *)
Out[ ]:
In [ ]:
transfo_mot "5241";;
Out[ ]:
Mais on peut aussi accélérer un peu :
In [ ]:
Array.init
Out[ ]:
In [ ]:
let transfo_mot (m : string) : mot =
Array.init (String.length m) (fun i -> (entier m.[i]))
(* Complexité temporelle et spatiale en O(p) *)
Out[ ]:
In [47]:
transfo_mot "5241";;
Out[47]:
In [48]:
let test_permut (m : string) : bool =
est_permut (trouve_omega (transfo_mot m));;
(* Complexité temporelle en O(p) *)
Out[48]:
In [110]:
let test_permut_mot (m : mot) : bool =
est_permut (trouve_omega m);;
(* Complexité temporelle en O(p) *)
Out[110]:
Quelques exemples :
In [49]:
test_permut "433";; (* pas jonglable *)
Out[49]:
In [52]:
test_permut "432";; (* pas jonglable *)
Out[52]:
In [53]:
test_permut "441";; (* jonglable *)
Out[53]:
In [50]:
test_permut "5241";; (* jonglable *)
Out[50]:
In [51]:
test_permut "9340";; (* jonglable *)
Out[51]:
In [67]:
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é *)
;;
Out[67]:
In [68]:
test_moyenne_mot [|5;4;3;0|] 3;;
Out[68]:
On va finir par quelques exemples :
In [69]:
let test_moyenne (m : string) (b : int) : bool =
test_moyenne_mot (transfo_mot m) b;;
Out[69]:
In [70]:
test_moyenne "433" 3;;
Out[70]:
In [71]:
test_moyenne "443" 3;;
Out[71]:
In [72]:
test_moyenne "432" 3;;
Out[72]:
In [73]:
test_moyenne "5430" 3;;
Out[73]:
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)$.
In [114]:
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
;;
Out[114]:
In [115]:
let partition balles p =
let debut = Array.make p (-1) in
partition_aux balles p debut 0 []
;;
Out[115]:
In [116]:
let bp balles p = List.filter test_permut_mot (partition balles p);;
Out[116]:
Par exemples :
In [117]:
partition 3 3;;
Out[117]:
In [118]:
bp 3 3;;
Out[118]:
On voit que l'on retrouve les mots donnés en exemples dans le texte, 441, 423, 333 par exemple :
In [124]:
List.mem [|4; 4; 1|] (bp 3 3);;
List.mem [|4; 2; 3|] (bp 3 3);;
List.mem [|3; 3; 3|] (bp 3 3);;
Out[124]:
Out[124]:
Out[124]:
Et le mot 433 n'est pas dans la liste calculée :
In [125]:
List.mem [|4; 3; 3|] (bp 3 3);;
Out[125]:
Pour $m=4$, on commence à avoir beaucoup plus de réponses :
In [121]:
partition 4 4;;
List.length (partition 4 4);;
Out[121]:
Out[121]:
In [123]:
bp 4 4;;
List.length (bp 4 4);;
Out[123]:
Out[123]:
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.