Discussion :

[guipe]

Re bonjour, j'ai à nouveau un petit problème d'algo je dirais.

Je dois faire le produit cartésien de deux listes.
Voici ce que j'ai fait :

Code :

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

1
2
3
4
let rec produit_cartesien l1 l2=
	 match (l1,l2) with
	 |([],_) | (_,[])-> []
	 |((h1::t1),(h2::t2)) -> (h1,h2) :: (produit_cartesien t1 h2 @ produit_cartesien l1 t2) ;; ;;

[Steki-kun]

Je suis pas sûr (même certain en fait) que ton problème vienne de Caml, tu as essayé d'écrire une définition "mathématique" récursive du produit cartésien de 2 ensembles finis ?
Petit truc pour savoir si ton code a la moindre chance d'être juste: on va faire un peu d'interprétation abstraite, je cherche même pas à comprendre ce que fait ta fonction, mais je regarde le nombre d'éléments dans le résultat, c'est sensé être n * m où n et m sont les longueurs des arguments. Or dans la deuxième branche on obtient:

1 + n * (m-1) + (n-1)*m

soit à peu près le double du nombre attendu d'éléments.

S.

[drunkskater]

Salut,

Je suis pas sûr que ce soit une bonne idée, mais en tous cas moi ça m'aide à écrire ce genre de fonctions :

Il faut balayer la première liste, mais à chaque étape il faudra également balayer la deuxième liste (d'où la complexité en n.m). Or c'est un peu compliqué à écrire d'un coup. Du coup ce que je fais c'est que plutôt que d'écrire une fonction compliquée, j'écris deux fonctions simples :

1. Une qui fait le "produit cartésien" d'un ensemble à un élément et d'un ensemble à m éléments (en fait le premier argument qu'elle prendra ne sera pas un ensemble à un élément mais tout simplement cet élément).

2. Une qui d'arguments un ensemble à n éléments et un ensemble à m élément va renvoyer le produit cartésien de ces deux ensembles : elle va balayer la première liste en appliquant la première fonction à chacun ses éléments (et à la deuxième liste).

L'avantage c'est que les deux fonctions sont super simples à écrire individuellement, donc globalement ça rend le problème simple.

Par contre je ne sais pas si c'est une bonne pratique, notamment je ne sais pas s'il vaut mieux définir la première fonction globalement ou localement... Je sais même pas si ça fait une différence, peut-être pour la lisibilité ?

Un code sera peut-être plus parlant mais attention, je ne garantis absolument pas que celui-ci est bon ! (par contre je l'ai essayé et a priori ça marche)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
let cart l1 l2 = 
  let rec aux1 h1 l2 l3 =
    match l2 with
    | [] -> l3
    | h2::t2 -> aux1 h1 t2 ((h1,h2)::l3)
  in
  let rec aux2 l1 l2 l3 =
    match l1 with
    | [] -> l3
    | h1::t1 -> aux2 t1 l2 (aux1 h1 l2 l3)
  in
  aux2 l1 l2 []
;;

[guipe]

Oui je sais bien j'ai bien dit que j'avais plutot un problème d'algo que de caml !

[gorgonite]

je verrais plutôt quelque chose dans ce style... écrit naïvement ça donnerait cela

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
# let rec produit_cartesien l1 l2=
 match (l1,l2) with
 |([],_) | (_,[])-> []
 |((h1::t1),(h2::t2)) -> (h1,h2) :: (produit_cartesien ([h1]) t2) @ (produit_cartesien t1 ([h2])) @ (produit_cartesien t1 t2)
;;
val produit_cartesien : 'a list -> 'b list -> ('a * 'b) list = <fun>
# produit_cartesien ([0;1;2]) (['a';'b']) ;;
- : (int * char) list =
[(0, 'a'); (0, 'b'); (1, 'a'); (2, 'a'); (1, 'b'); (2, 'b')]
#

pas dur d'optimiser (beaucoup) ce code... à toi de jouer

[guipe]

Ta fonction renvoit [(0, 'a'); (0, 'b'); (1, 'a'); (2, 'a'); (1, 'b'); (2, 'b')].

Or elle devrait renvoyer [(0, 'a'); (1, 'a'); (2, 'a'); (0, 'b'); (1, 'b'); (2, 'b')].

[guipe]

Voilà ce que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
 
let l1= ["a";"b"] ;;
let l2 = [1;2;3];;
 
 
let rec produit_cartesien l1 l2=
		match (l1,l2) with
		|([],_) | (_,[])-> []
		|((h1::t1),(h2::t2)) -> (h1,h2):: (produit_cartesien t1 ([h2]) @ produit_cartesien ([h1]) t2 @ produit_cartesien t1 t2);

Mais ça me renvoit ["a", 1; "b", 1; "a", 2; "a", 3; "b", 2; "b", 3] au lieu de

["a", 1; "b", 1; "a", 2; "b", 2; "a", 3; "b", 3].

Je n'y arrive pas,franchement je commence à désespérer...

[guipe]

Aleluia j'y suis enfin arrivé,comme quoi meme moi ... bref.

J'ai opté pour faire une sous fonction qui fait le produit cartésien entre une liste et un singleton.Ensuite je l'ai utilisé pour faire le produit cartésien des deux listes.

Voici:

Code :

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

1
2
3
4
5
6
7
8
9
let rec fonction l n =
	match l with
	|[] -> []
	|(head::tail) -> (head,n)::(fonction tail n);;
 
let rec produit_cartesien l1 l2=
	match (l1,l2) with
	|([],_) | (_,[])-> []
	|((h1::t1),(h2::t2)) -> fonction l1 h2 @ produit_cartesien l1 t2;;

Bref ouf merci à vous !

[Cacophrene]

Bonsoir,

Vraiment à la va-vite, parce que je n'ai vraiment pas beaucoup de temps à y consacrer, il me semble que tu peux optimiser ce code avec un système de type continuations (en gros tu passes à chaque fonction la liste en construction pour éviter une coûteuse concaténation). Ça va tout rendre tail-rec. Je te donne le code auquel je pense, pas testé donc prudence (en fait je soupçonne que le résultat est le bon mais l'ordre inversé) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
let rec fonction n acc = function
  | [] -> acc
  | head :: tail -> fonction n ((head, n) :: acc) tail
 
let produit_cartesien l1 l2 =
  let rec loop acc l1 l2 =
    match l1, l2 with
    | [], _ | _, [] -> acc
    | _, h2 :: t2 -> loop (fonction h2 acc l1) l1 t2
  in loop [] l1 l2

Je n'ai malheureusement pas le temps de détailler le pourquoi du comment de ce code.

Cordialement,
Cacophrène

[gorgonite]

Ta fonction renvoit [(0, 'a'); (0, 'b'); (1, 'a'); (2, 'a'); (1, 'b'); (2, 'b')].

Or elle devrait renvoyer [(0, 'a'); (1, 'a'); (2, 'a'); (0, 'b'); (1, 'b'); (2, 'b')].

depuis quand l'ordre importe ?

[LLB]

Depuis que l'on renvoie une liste.

[gorgonite]

Depuis que l'on renvoie une liste.

la liste n'est pas juste une représentation interne de l'ensemble ?
c'est souvent le cas dans les TD pour débutants (il faut alors qu'ils fassent attention aux doublons )

par ailleurs, rien ne dit que la liste est ordonnée, et donc que l'on doit s'attarder sur la façon de mettre les éléments dans le résultat final

[Steki-kun]

Je plussoie Gorgonite !
Et d'ailleurs j'ajoute que si ces listes ne sont pas des ensembles finis, il aurait fallu définir ce que ça veut dire que produit cartésien