Bonjour/bonsoir,

en cours je travaille depuis quelques semaines sur le logiciel Ocaml qui ne semble pas être évident à prendre en main; en tout cas j'ai du mal a ecrire moi-même des programmes.
Je sais qu'il y a le forum Cours et Devoirs, mais je pense truver plus de personne susceptibles de connaitre le langage Caml ici.

L'exercice porte sur les sous-séquence:

Si A est une liste de n éléments, on appelle sous-séquence de A toute liste obtenue en retirant un nombre quelconque (eventuellement nul) d'éléments de A et en conservant l'ordre.
Par exemple, si A=(a,b,c,d,e) alors des sous-séquences sont la liste vide , (a,d,e), (a,c). (b,a) n'en est pas une .

Il faut premièrement ecrire un algorithme qui a partir de deux listes A et C permet de savoir si C est une sous-séquence de A (et je pense que dans un premier temps il n'a pas besoin d'être intéressant au niveau du temps de calcul)

J'avoue ne vraiment pas savoir par quoi débuter. A priori je pense qu'il faut programmer en recursif puisqu'on n'a fait que ça jusqu'à présent...
Cependant je ne vois vraiment pas comment faire, ne voyant pas le mécanisme permettant de remonter à un cas simple à chaque fois. D'ailleurs, j'ai même du mal à identifier ces cas simples:
si on appelle f la fonction, je pense que f A [] qui renvoie "true" en serait un, pour celui qui renverrait "false" je ne sais pas...

Merci d'avance pur toute aide

j'ai fait du caml, mais c'etait il y a longtemps. Mais, il y a des caml-eux experimente qui passe souvent par ici.

Pour vérifier que le sous-séquent est dans la liste de A, tu as juste à tester l'inclusion du sous-séquent dans la liste

Voilà comment tu peux procéder:

(* Longueur d'une liste *)
let rec longueur = function l -> match l with
[]->0
|a::b-> 1+ longueur b;;

(* Vérifie qu'un élement appartient à la liste *)
let rec appartient = function (e,l) -> match l with
[]-> false
|a::b -> if (a=e) then true else appartient(e,b);;

(* On vérifie que C est inclus dans A *)
let rec inclus = function (c,a) -> match c with
[] -> true
|e::l -> if(longueur(c)>longueur(a)) then false
else
if(appartient(e,a)) then inclus(l,a)
else false;;

En espérant avoir répondu à ta question

Merci beaucoup !
Je pense avoir compris le principe de l'algorithme inclus. Cependant il ne tient pas compte de l'ordre.
Ainsi, " inclus ([2;1],[1;2]);; " me renverra true alors qu'il devrait pas.

Ce n'est pas la peine de prendre du temps pour le modifier, je pense pouvoir trouver ce qui est à modifier.
Encore merci

Voilà. Si dans l'avant dernière ligne de code on ne prend pas la liste a mais seulement sa queue ça semble marcher.

Désolé des trois messages à la suite, seulement je viens de me rendre compte que cette modification n'était pas suffisante.
En effet, il faut ne faut en réalité pas forcément prendre la queue de a une seule fois pour que cela marche.

Je réécris le code - dont j'avais au passage un peu modifié la syntaxe pour être plus à l'aise - et avec quelques ajouts pour qu'on y comprenne quelque chose:

let rec longueur l = match l with
[] -> 0
| t :: q -> succ (longueur q);;

let rec appartient e l = match l with
[] -> false
| t :: q -> if t = e then true
else appartient e q;;

(*prend la queue d'une liste *)
let queue l = match l with
[] -> []
| t :: q -> q;;

(*calcule f^n(x) = (f o f o ... f)(x) *)
let rec compose f n x = match n with
0 -> x
| _ -> f (compose f (n - 1) x);;

(*c sous sequence de a ? *)
let rec ss_seq c a = match c with
[] -> true
| t :: q -> if longueur c > longueur a then false
else if appartient t a then ss_seq q (compose queue N a) (*il faut trouver N, nombre de fois où la fonction queue sera appliquée à la liste a *)
else false;;

En effet, si on prend N=1 (cas où la fonction compose est inutile), on aura par exemple
ss_seq [3;4;1] [3;1;4;5];; qui renverra normalement false
mais ss_seq [3;5;4] [3;1;4;5];; qui renverra true. J'arrive a comprendre le problème, cependant je ne vois pas comment exprimer la variable locale N.

je ne comprends pas trop ce que tu cherches à faire. L'idée est de décomposer en cas de base et de regarder ce qui se passe (et ça s'exprimera très bien avec du pattern matching). Par exemple, une liste vide est une sous séquence de n'importe quoi (y compris une liste vide). Inversement, rien (sauf la liste vide) n'est sous séquence de la liste vide. Ensuite, il te reste juste à regarder les éléments en tête de tes listes : s'ils sont les mêmes tu les enlèves et tu regarde la suite, sinon, tu enlèves seulement un élements sur la liste (pas la possible sous séquence dont tu dois vérifier chaque éléments).

Au final, tu as quelque chose comme ça :

let rec est_sous_seq a b =
match a, b with
| _, [] -> true
| [], _ -> false
| a::s, b::t when a = b -> est_sous_seq s t
| _::s, t -> est_sous_seq s t

On peut noter que dans le troisième cas, il serait possible d'écrire : est_sous_seq s t || est_sous_seq s (b::t)
Car on n'est pas obligé de matcher la tête de la sous séquence sur le premier éléments identique dans la liste. Mais ce n'est pas utile car il n'y a pas de possibilité de trouver une sous séquence par se moyen qu'on ne verrait pas sinon (la preuve est laissé en exercice).

(bon, je ne comptais pas de donner la solution, mais je pensais que tu en avais trouver une et je voulais te montrer un moyen plus concis, et en lisant mieux j'ai vu que tu n'avais pas de solution fonctionnelle, bref, comme la méthode plus concise était là, tu l'as)

Merci !
Je vais bien essayer de comprendre le programme, très condensé par rapport à ce que j'avais enfin trouvé, et surement bien plus efficace.

Simplement pour information, avec les fonctions définies précédemment j'étais arrivé à un programme qui marche mais au final bien compliqué :

(* 1ère rang auquel on trouve un élément e dans une liste l *)
let rec rang e l = match l with
[] -> 0
| t :: q -> if t = e then 1 else rang e q + 1;;

(* verifie si une liste c est sous-sequence d'une liste a *)
let rec ss_seq c a = match c with
[] -> true
| t :: q -> if longueur c > longueur a then false
else if appartient t a then ss_seq q (compose queue (rang t a) a) (*si on a une sous sequence t::q dont le premier terme t apparait au rang p dans a, alors on regarde si q est une sous-sequence dans les n-p élèments de a restant *)
else false;;