Discussion :

[Mamadou Dian]

Bonjour, au fait j'ai un petit souci. Je voudrais savoir comment faire pour comparer 2 listes en caml et comment vérifier que la 1ère est inclue dans la 2ème.
Merci pour votre aide

[TchoubiTchoub]

Bonjour,

Les deux choses que tu demandes sont sensiblement différentes. Savoir si une liste est incluse dans une autre peut prendre différents sens

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[1;2;3] est incluse dans [0;1;4;2;5;3] mais pas dans [1;3;2;4]

(inclusion avec respect de l'ordre)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[1;2;3] est incluse dans [0;1;4;2;5;3] et aussi dans [1;3;2;4]

(inclusion sans notion d'ordre (inclusion ensembliste))

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

[1;2;3] n'est pas incluse dans [0;1;4;2;5;3] mais est incluse dans [1;2;3;5;4]

(inclusion en terme de reconnaissance d'un sous-mot dans un mot))

Quelle est donc exactement ta question ?

Pour ce qui est de comparer deux listes, il faut aussi être précis. Comparer en terme de longueur ? En terme d'ordre lexicographique ?

Cordialement

[Mamadou Dian]

En gros pour la comparaison c'est une fonction (equal) qui renvoie un booléen. Par exemple equal s1 s2 est vraie si et seulement si s1 et s2 contiennent les mêmes éléments et en même nombre et pour vérifier si la 1ère est incluse dans la 2ème voici ce que j'ai fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let rec inclus (s1 : 'e mset) (s2 : 'e mset) : bool =
	match (s1,s2) with
	| (Nil,Nil) -> true
	| (Cons((x,y),p),Nil) -> false
	| (Nil,Cons((x,y),p)) -> true
	| (Cons((a,b),p),Cons((c,d),q)) -> ( if a=c then inclus p q
					                  else inclus (Cons((a,b),p)) q )  ;;

[SpiceGuid]

Pour l'égalité de liste, de deux choses l'une :
● Ou bien la fonction (=) fait l'affaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# [1;2] = [2;1];;
- : bool = false

● Ou bien ton égalité c'est l'inclusion réciproque :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# let equal la lb = includes la lb && includes lb la;;
val equal : 'a list -> 'a list -> bool = <fun>

[TchoubiTchoub]

En gros pour la comparaison c'est une fonction (equal) qui renvoie un booléen. Par exemple equal s1 s2 est vraie si et seulement si s1 et s2 contiennent les mêmes éléments et en même nombre et pour vérifier si la 1ère est incluse dans la 2ème voici ce que j'ai fais :

let rec inclus (s1 : 'e mset) (s2 : 'e mset) : bool =
match (s1,s2) with
| (Nil,Nil) -> true
| (Cons((x,y),p),Nil) -> false
| (Nil,Cons((x,y),p)) -> true
| (Cons((a,b),p),Cons((c,d),q)) -> ( if a=c then inclus p q
else inclus (Cons((a,b),p)) q ) ;;

Bon, on voit clairement que tu débutes ;-) (notamment, OCaml est un langage fortement typé avec inférence de type. Cela signifie que tu n'as à donner aucun type, OCaml les trouvera tout seul à la compilation)

Comme te l'a dit SpiceGuid, tu peux utiliser l'égalité structurelle (i.e. =) (pas l'égalité physique, ==, qui est une erreur fréquente quand on passe de C à OCaml)

Pour l'égalité, on parle donc bien de double inclusion en terme ensembliste mais ta fonction inclus ne me semble pas correcte. Je vais donc déjà la réécrire façon OCaml (tu verras que c'est beaucoup plus lisible)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec inclus l1 l2 = 
match (l1, l2) with
| [], _ (* _ veut dire que la liste l2 peut être ce qu'on veut, ce qui correspond donc à ton premier et ton troisième cas *) -> true
| _, [] -> false
| a::tl1, c::tl2 -> if a = c then inclus tl1 tl2 else inclus l1 tl2
(* Je vois que tu manipules des listes de couples mais pour plus de lisibilité j'ai mis des listes d'entiers *)

Cette comparaison correspond à l'inclusion avec respect de l'ordre mais si on prend l'expression suivante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

inclus [1;2] [2;1]

elle renverra faux.

Si tu es obligé de manipuler des listes, je t'invite à remarquer que pour chaque élément de l1 tu vas devoir parcourir l2 jusqu'à trouver un élément égal, le supprimer de l2 et recommencer avec le reste des éléments de l1.

Pour l'égalité, soit tu fais une double inclusion soit tu remarques que dans le code de ton inclusion précédente, la différence entre l'inclusion et l'égalité est qu'on s'arrête en répondant true uniquement si les deux listes sont vides.

Cordialement

[Mamadou Dian]

Bon, on voit clairement que tu débutes ;-) (notamment, OCaml est un langage fortement typé avec inférence de type. Cela signifie que tu n'as à donner aucun type, OCaml les trouvera tout seul à la compilation)

Comme te l'a dit SpiceGuid, tu peux utiliser l'égalité structurelle (i.e. =) (pas l'égalité physique, ==, qui est une erreur fréquente quand on passe de C à OCaml)

Pour l'égalité, on parle donc bien de double inclusion en terme ensembliste mais ta fonction inclus ne me semble pas correcte. Je vais donc déjà la réécrire façon OCaml (tu verras que c'est beaucoup plus lisible)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec inclus l1 l2 = 
match (l1, l2) with
| [], _ (* _ veut dire que la liste l2 peut être ce qu'on veut, ce qui correspond donc à ton premier et ton troisième cas *) -> true
| _, [] -> false
| a::tl1, c::tl2 -> if a = c then inclus tl1 tl2 else inclus l1 tl2
(* Je vois que tu manipules des listes de couples mais pour plus de lisibilité j'ai mis des listes d'entiers *)

Cette comparaison correspond à l'inclusion avec respect de l'ordre mais si on prend l'expression suivante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

inclus [1;2] [2;1]

elle renverra faux.

Cordialement

Au fait j'arrive vraiment pas à comprendre pourquoi

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

inclus [1;2] [2;1]

retourne false alors qu'on a les mêmes éléments dans les 2 listes. Comment faire alors une inclusion sans respect d'ordre pour que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

inclus [1;2;3] [3;1;2]

retourne vrai .
Merci pour votre aide !

[TchoubiTchoub]

Dans ton code, ce que tu fais c'est la chose suivante (en pseudo code)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
inclus l1 l2 =
si l1 est vide alors on renvoie vrai
sinon si l2 est vide (donc l1 n'est pas vide) on renvoie faux (car il existe des éléments de l1 qu'on n'a pas vu dans l2)
sinon soit e1 :: tl1 = l1 et e2 :: tl2 = l2
  si e1 = e2 on renvoie le résultat de inclus tl1 tl2
  sinon on renvoie le résultat de inclus l1 tl2

Avec les listes [1;2] et [2;1], la pile d'appels successifs donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
inclus [1; 2] [2; 1] =
  (1 <> 2) donc on appelle inclus [1;2] [1]
     (1 = 2) donc on appelle inclus [2] []
        (l2 = []) donc on renvoie faux

Ce qu'on aurait voulu c'est plutôt

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
inclus [1; 2] [2; 1] =
  (1 appartient à [2; 1]) donc on appelle inclus [2] [2]
     (2 appartient à [2]) donc on appelle inclus [] []
        (l1 = []) donc on renvoie vrai

Je te laisse réfléchir sur la façon de faire ça ? (à vrai dire, à moins que tu sois vraiment obligé de manipuler des listes, ce test d'inclusion est bien plus efficace sur les ensembles. Sur les listes on a une complexité en O(n²), c'est vraiment pas optimal)

[Mamadou Dian]

Je crois que j'ai trouvé une solution, j'ai défini d'abord une fonction app qui vérifie si un élément appartient à une liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec app ( e : 'e ) ( s : 'e mset ) : bool =
	match s with
	| Nil -> false
	| Cons((a,b),p) -> e=a || member e p    ;;

Ensuite je l'ai utilisé dans la foction "inclus"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec inclus (s1 : 'e mset) (s2 : 'e mset) : bool =
	match (s1,s2) with
	| (Nil,_) -> true
	| (Cons((x,y),p),Nil) -> false
	| (Cons((a,b),p),Cons((c,d),q)) -> ( if app a (Cons((c,d),q)) then inclus p (Cons((c,d),q))
					     else false  ;;

et ça a l'air de bien marcher.

[TchoubiTchoub]

Je crois que j'ai trouvé une solution, j'ai défini d'abord une fonction app qui vérifie si un élément appartient à une liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let rec app ( e : 'e ) ( s : 'e mset ) : bool =
	match s with
	| Nil -> false
	| Cons((a,b),p) -> e=a || member e p    ;;

Ensuite je l'ai utilisé dans la foction "inclus"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
let rec inclus (s1 : 'e mset) (s2 : 'e mset) : bool =
	match (s1,s2) with
	| (Nil,_) -> true
	| (Cons((x,y),p),Nil) -> false
	| (Cons((a,b),p),Cons((c,d),q)) -> ( if app a (Cons((c,d),q)) then inclus p (Cons((c,d),q))
					     else false  ;;

et ça a l'air de bien marcher.

Ca a l'air mais ça ne marchera pas comme voulu

Bon, déjà, il faudrait que tu penses à utiliser les modules standards d'OCaml (notamment, dans ton cas, le module List )

Si je réécris ton code avec ce module j'ai la chose suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let rec app e l =
  match l with
  |[] -> false
  |(e', _) :: tl -> e = e' || app e tl
;;
 
let rec inclus l1 l2 =
  match l1, l2 with
  | [], _ -> true
  | _, [] -> false
  | (a, _)::tl1, l2 -> app a l2 && inclus tl1 l2
;;

(Déjà, c'est plus lisible, non ?)

Alors, où se situe le problème ?

Si je fais inclus [(1, "a")] [(1, "b"); (1, "c")] je voudrais obtenir vrai et, comme prévu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# inclus [(1, "a")] [(1, "b"); (1, "c")];;
- : bool = true

Mais si je fais inclus [(1, "b"); (1, "c")] [(1, "a")] je voudrais obtenir faux, non ? Pourtant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
# inclus [(1, "b"); (1, "c")] [(1, "a")];;
- : bool = true

Car ce que tu oublies de faire c'est de supprimer dans l2 l'élément qui t'a permis de renvoyer vrai avec app.

Il faut donc modifier app pour qu'elle te renvoie un booléen plus la nouvelle liste l2 dans laquelle n'apparaît plus l'élément e'.

Sinon, une autre solution, c'est de trier les deux listes et de faire un seul parcours

Je t'invite à tester ces deux solutions (sans tes types forcés, on est en OCaml, pas en C, Java etc.)