Aller au contenu

Les fonctions sont à écrire en OCaml. Chaque question de programmation est suivie de tests qui doivent passer sans erreur.

Palindromes

On dit qu'un tableau t est un palindrome quand il comporte les éléments dans le même ordre qu'on le lise de droite à gauche ou de gauche à droite. Par exemple [|0;1;2;1;0|] est un palindrome mais [|0;1;2|] n'en est pas un.

On vous demande ici de programmer de deux manières une fonction palindrome : 'a array -> bool qui détermine si un tableau est un palindrome.

Question 1. Tout d'abord, on va programmer la fonction impérativement en s'appuyant sur une référence pour vérifier dans une boucle si le tableau est un palindrome.

Corrigé 
let palindrome t =
    let n = Array.length t in
    let check = ref true in
    for i = 0 to n / 2 - 1 do
        check := !check && t.(i) = t.(n-i-1)
    done;
    !check

Tests :

assert(palindrome [|0;1;2;1;0|]);
assert(not (palindrome [|1;2|]));
assert(not (palindrome [|1;3;2|]));
assert(palindrome [||]);
assert(palindrome [|1|]);
assert(palindrome [|0;1;1;0|]);
assert(palindrome [|"a";"b";"b";"a"|])

Question 2. Prouver la correction de votre fonction et donner sa complexité.

Corrigé

Notons \(n\) la longueur de t. Le tableau est un palindrome si et seulement si \(\forall k \in \range{0}{n-1},\ t_k = t_{n-1-k}\). Comme cette condition est symétrique en \(k\) et \(n-1-k\), et triviale pour \(k = n-1-k\) (élément central quand \(n\) est impair), il suffit de la vérifier pour \(k \in \range{0}{\lfloor n/2 \rfloor - 1}\).

La boucle for termine. On montre l'invariant suivant : au début de l'itération d'indice \(i\), !check vaut vrai si et seulement si \(\forall k \in \range{0}{i-1},\ t_k = t_{n-1-k}\).

  • Pour \(i = 0\), !check vaut true et l'intervalle est vide.
  • Si l'invariant est vrai au début de l'itération \(i\), après l'affectation !check vaut vrai si et seulement si l'ancienne valeur est vraie et \(t_i = t_{n-1-i}\), c'est-à-dire si et seulement si \(\forall k \in \range{0}{i},\ t_k = t_{n-1-k}\).

En sortie de boucle, l'invariant est vérifié pour \(i = \lfloor n/2 \rfloor\) (y compris quand la boucle n'est pas exécutée, pour \(n \le 1\)), donc la fonction renvoie bien la bonne valeur.

Il y a \(\lfloor n/2 \rfloor\) itérations, chacune en temps constant pour des éléments de taille bornée (la comparaison = sur des chaînes, par exemple, a un coût proportionnel à leur longueur). La complexité est donc en \(O(n)\). On remarque qu'on ne s'arrête pas à la première différence : on pourrait utiliser une boucle while pour cela.

Question 3. Maintenant, on va programmer la fonction à l'aide d'une fonction récursive (on peut la définir en dehors de la fonction palindrome ou comme une variable locale à l'intérieur de palindrome).

Corrigé

Grâce à l'évaluation paresseuse de &&, on s'arrête ici à la première différence.

let palindrome t =
    let n = Array.length t in
    let rec check i =
        if i < n/2
        then t.(i) = t.(n-i-1) && check (i+1)
        else true
    in check 0

Tests : les mêmes que pour la question 1.

Anagrammes

On dit qu'un tableau est un anagramme d'un autre s'ils contiennent les mêmes éléments à une permutation près.

Ainsi [|1;2;3;4|] et [|4;3;2;1|] sont des anagrammes. Cela se complique quand on considère des tableaux ayant plus d'une fois la même valeur, par exemple [|1;2;1|] et [|2;1;1|] sont des anagrammes.

Question 4. Dans un premier temps, on fait l'hypothèse que les tableaux ne contiennent jamais deux fois la même valeur et qu'ils sont de même longueur. Écrire une fonction anagramme : 'a array -> 'a array -> bool.

Corrigé

Sous ces hypothèses, il suffit de vérifier que chaque élément de t1 est présent dans t2.

let anagramme t1 t2 =
    let n = Array.length t1 in
    let valide = ref true in
    for i = 0 to n-1 do
        let found = ref false in
        for j = 0 to n-1 do
            if t2.(j) = t1.(i)
            then found := true
        done;
        valide := !found && !valide
    done;
    !valide

Tests :

assert(anagramme [|1;2;3;4|] [|1;2;3;4|]);
assert(anagramme [|1;2;3;4|] [|4;3;2;1|]);
assert(not (anagramme [|1;2;3;4|] [|1;2;3;5|]));
assert(anagramme [||] [||]);
assert(anagramme [|"c";"b";"a"|] [|"a";"b";"c"|])

Question 5. Quelle est la complexité de votre fonction anagramme ?

Corrigé

Les deux boucles imbriquées effectuent exactement \(n^2\) itérations en temps constant : la complexité est en \(O(n^2)\).

Question 6. On suppose maintenant que les valeurs peuvent se répéter, mais on suppose également que les tableaux ne contiennent que des valeurs entières positives strictement plus petites que 100. Écrire une nouvelle fonction anagramme.

Indication : comptez les éléments.

Corrigé 
let anagramme t1 t2 =
    let n = Array.length t1 in
    let compte = Array.make 100 0 in
    let compte2 = Array.make 100 0 in
    for i = 0 to n-1 do
        compte.(t1.(i)) <- 1 + compte.(t1.(i));
        compte2.(t2.(i)) <- 1 + compte2.(t2.(i))
    done;
    let valide = ref true in
    for i = 0 to 99 do
        valide := !valide && compte.(i) = compte2.(i)
    done;
    !valide

Tests :

assert(anagramme [|1;2;3;4|] [|1;2;3;4|]);
assert(anagramme [|1;2;3;4|] [|4;3;2;1|]);
assert(not (anagramme [|1;2;3;4|] [|1;2;3;5|]));
assert(anagramme [|1;2;2;4|] [|4;2;2;1|]);
assert(anagramme [|99;99;99;99|] [|99;99;99;99|]);
assert(not (anagramme [|1;2;1;1|] [|1;2;2;1|]));
assert(anagramme [||] [||])

Question 7. Quelle est la complexité de cette nouvelle fonction anagramme ?

Corrigé

La création des deux tableaux de comptage et la seconde boucle coûtent \(O(100)\), la première boucle \(O(n)\) : la complexité est en \(O(n + 100) = O(n)\). Plus généralement, si les valeurs sont strictement inférieures à \(M\), on obtient \(O(n + M)\), comme pour le tri par comptage.

Question 8. On considère maintenant une 'a list plutôt qu'un 'a array, mais dont les éléments sont uniques. Écrire une fonction genere_anagramme : 'a list -> 'a list list permettant de renvoyer la liste de tous les anagrammes de la liste donnée.

Par exemple, étant donné la liste [1;2;3], on devra renvoyer :

[ [1;2;3]; [1;3;2]; [2;1;3];
  [2;3;1]; [3;1;2]; [3;2;1] ]
Corrigé

Pour chaque élément t de la liste, on génère les anagrammes de la liste privée de t et on place t en tête de chacun d'eux.

let rec genere_anagramme l =
    let rec enleve l x =
        match l with
        | [] -> []
        | y::q -> if x = y then q else y :: enleve q x
    in
    let rec anag_aux l1 =
        match l1 with
        | [] -> [ ]
        | t::q -> List.map (fun m -> t::m) (genere_anagramme (enleve l t))
                  @ anag_aux q
    in
    match l with
    | [] -> [ [] ]
    | _ -> anag_aux l

Une variante avec des fonctions mutuellement récursives :

let rec enleve l x =
    match l with
    | [] -> []
    | t::q -> if t = x
              then q
              else t::enleve q x

let rec gen_aux l lorig =
    match l with
    | [] -> []
    | x::q ->
            List.map (fun r -> x::r)
                (genere (enleve lorig x))
            @ gen_aux q lorig
and genere l = if l = [] then [ [] ]
               else gen_aux l l

Test :

assert(genere_anagramme [1;2;3] =
  [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]])