Discussion :

[elishac]

Bonjour,

Je cherche à programmer une fonction qui prenne en argument 2 ensembles, l'un étant des nombres (réels), l'autre des opérations (supposées binaires pour l'instant, par exemple +.,-.,*.), et qui rende l'ensemble des résultats différents qui peuvent être construits en utilisant une et une seule fois chaque nombre (dans l'ordre que l'on veut), et les opérations autant de fois que l'on veut. (Exemple : pour {1,3,4,6} et {+.,*.,/.,-.}, 24 est une solution ;-) ).
Pour ce faire, je me suis dit qu'un algorithme de base était de lister toutes les possibilités, pour ensuite les évaluer, enlever tous les doublons, bref, travailler sur l'ensemble trouvé. Appelons liste_des_formules la fonction qui prend en argument l'ensemble E des scalaires et F l'ensemble des lois de composition interne, et qui rend la liste de toutes les formules qu'il est possible de faire, avec les contraintes énoncées plus haut.
La représentation que j'ai choisi pour les formules est celle d'arbre binaire (les noeuds seront les lois de composition, et les feuilles seront les scalaires).
Considérons dans un premier temps qu'il n'existe qu'une seule loi de composition lc.
De manière récursive, lorsqu'on a n scalaires, on obtient "liste_des formules E n" (avec E de cardinal n) en étudiant toutes les partitions de E.
Considérons que la fonction partition : 'a list -> ('a list * 'a list) list = <fun> qui permet de donner l'ensemble des partitions en 2 éléments d'un ensemble existe déjà.
Pour bien comprendre ce que fait la fonction partition, voici un exemple :

Code :

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

1
2
3
4
#partition [1;2;3];;
- : (int list * int list) list =
 [[], [1; 2; 3]; [3], [1; 2]; [2], [1; 3]; [2; 3], [1]; [1], [2; 3];
  [1; 3], [2]; [1; 2], [3]; [1; 2; 3], []]

Par ailleurs, pour ceux qui voudraient faire des tests sur leur machine, je vous propose la fonction partition suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
let partition l=
let rec parties l = (*fonction qui donne l'ensemble des parties d'un ensemble*)
 let rec ajout a = function
  | [] -> []
  | (liste1 :: tl) -> (a :: liste1) :: (ajout a tl)
 in
 match l with
 |[]->[[]]
 |t::q->let mem=(parties q) in  mem @ (ajout t mem)
in
let rec appartient a=function (*fonction de base, qui dit si un élément est dans une liste*)
 |[]->false
 |b::q->if a=b then true else appartient a q
in
let construire_complementaire l1 l2 = (*fonction qui donne le complémentaire d'un ensemble l1 dans un ensemble l2*)
let rec complementaire l1 l2= match l2 with
 |[]->[]
 |a::q->if (appartient a l1) then complementaire l1 q
        else a::(complementaire l1 q)
in
(l1,complementaire l1 l2)
in
 let rec f=function (*fonction partition définie à partir des fonctions précédentes*)
  |[]->[]
  |a::q->(construire_complementaire a l)::(f q)
 in
 f (parties l);;
partition [1;2;3];;

Par ailleurs, j'ai également fait ces petites fonctions dont je ne suis pas sûr :
- Une fonction qui évalue une formule, et qui servira plus tard (je n'ai volontairement pas utilisé la division, car la division par zéro pose problème, alors que les autres sont définies partout).

Code :

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

1
2
3
4
5
6
7
let rec eval formule = match formule with   
 |x->x
 |(a, lc, b) -> match lc with
  |add -> (eval a) +.(eval b)
  |mult -> (eval a) *.(eval b)
  |sous -> (eval a) -.(eval b)
  |div -> (eval a) /.(eval b);;

- Une fonction qui définit le type loi de composition :

Code :

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

1
2
3
4
5
type 'a lc = 
 |add of 'a * 'a 
 |mult of 'a * 'a 
 |sous of 'a * 'a 
 |div of 'a * 'a ;;

Enfin, la fonction qui est censée donner toutes les formules possibles :

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 formule f lc = match F with
 |[x] ->[x] 
 |_-> 
  let rec f (partie_fixe, lc, partie_variant) = match partie_variant with 
   |[x] ->[x] 
   | triplet1 ::q->(partie_fixe, lc, triplet1) :: (f (partie_fixe, lc, q))
  in
  let rec pour_chaque_partition=function
   |[ ]->[ ]
   |couple1 :: q-> let couple1 = (partie1,partie2) in
    (f partie1 (f partie2 partie1)) @ (pour_chaque_partition q)
  in
  pour_chaque_partition (partition f);;

Après cette petite introduction sur ce que je veux faire, ma question est alors la suivante : Pouvez-vous m'aider à continuer mon programme (pour l'instant, la fonction "formule" ne marche pas), me dire éventuellement ce qui ne va pas ou ce qui peut être amélioré, et ensuite dans un deuxième temps m'aider à généraliser (on a fait pas mal de cas particuliers : une seule loi pour l'instant, toujours pas d'écriture du programme qui donne l'ensemble des solutions recherchées, mais simplement l'ensemble des formules possibles, que des opérations binaires, etc...).

Merci d'avance pour votre aide.

[SpiceGuid]

L'intitulé correct de ton problème est arbres d'expressions arithmétiques, tu ne pourras donc pas le résoudre en utilisant exclusivement des listes.

Dans un arbre d'expression arithmétique:

• les feuilles sont des nombres
• les noeuds sont des opérateurs

Soit n la longueur de ta liste de nombres.
Ton travail comporte trois étapes:

• générer tous les arbres qui possèdent n feuilles
• décorer les n feuilles avec toutes les permutations possibles des n nombres
• décorer les noeuds avec tous les choix possibles parmi les 4 opérateurs

[elishac]

Je ne comprends pas très bien ton intervention. Affirmes-tu que ma méthode ne marche pas ?
Pour moi, une expression algébrique est soit (définition récurrente) un nombre, soit un triplet (g,lc,d), où g est une expression algébrique, lc une loi de composition, et d une autre expression algébrique (celle de droite, dans le cas où lc n'est pas commutative).

[Jedai]

Tu as une bonne approche du problème dans ce cours, c'est en Haskell, mais c'est transcriptible en OCaml relativement facilement.
(Tu cherches les solutions d'un jeu type "Des Chiffres et des Lettres" non ?)

Ton type de "loi de composition" est erronée, il n'y a qu'à voir comment tu fais le match dans ton eval. D'ailleurs quel peut bien être le type de ton eval...

--
Jedaï

[elishac]

Tu as une bonne approche du problème dans ce cours, c'est en Haskell, mais c'est transcriptible en OCaml relativement facilement.

Où ça? Je suis motivé, mais pas au point de lire 250 pages, même si c'est écrit gros :-).

(Tu cherches les solutions d'un jeu type "Des Chiffres et des Lettres" non ?)

Presque. Dans des chiffres et des lettres, je crois que tu peux n'utiliser que 2 nombres si tu veux. Dans mon énoncé, on est obligé d'utiliser exactement tous les scalaires proposés, sans répétition (mais dans l'ordre que l'on veut, par contre).

Ton type de "loi de composition" est erronée, il n'y a qu'à voir comment tu fais le match dans ton eval. D'ailleurs quel peut bien être le type de ton eval...

Comment le corriger, dans ce cas ?

[Jedai]

Où ça? Je suis motivé, mais pas au point de lire 250 pages, même si c'est écrit gros :-).

Il y a 250 pages ok, mais il n'y a qu'une petite dizaine de chapitres (signets), tu aurais pu lire le début de chaque même si tu ne savais pas que "Des chiffres (et des lettres)" est "The Countdown Problem", sans parler du fait que mon lien contenait un numéro de page (même si ça n'a apparemment pas marché).

Presque. Dans des chiffres et des lettres, je crois que tu peux n'utiliser que 2 nombres si tu veux. Dans mon énoncé, on est obligé d'utiliser exactement tous les scalaires proposés, sans répétition (mais dans l'ordre que l'on veut, par contre).

Non, dans DCEDL, tu peux utiliser autant de nombres que tu veux, sans répétitions par contre.

--
Jedaï

[elishac]

C'est bien ce que je dis, dans DCEDL, tu peux utiliser autant de nombres que tu veux parmi la liste proposée, alors que, dans mon énoncé à moi, tu es obligé d'utiliser une fois et une seule chaque nombre (le 'une seule', c'est ce que tu appelles 'sans répétition').

Par conséquent, peut-être que ton lien n'est pas adapté?


Tu as raison, j'ai pas fait attention, mais le pdf est effectivement sur une page précise.
J'ai parcouru rapidement les règles qui sont expliquées juste après, voici ce qui diffère des miennes :
- comme je viens de le dire, j'oblige l'utilisation de tous les nombres, alors que dans des chiffres et des lettres, ce n'est pas le cas.
- j'autorise de passer par des réels, même si je veux un résultat entier (contrairement à : "All the numbers, including intermediate results, must be positive naturals ").
Je viens juste de remarquer que j'avais oublié de dire ça dans mon introduction. Il faudra donc faire un test pour vérifier si le résultat trouvé est entier, avant de l'ajouter aux solutions.

[Jedai]

Par conséquent, peut-être que ton lien n'est pas adapté?

Tu as au moins des types corrects, plus une approche qui peut facilement être adaptée pour ton problème.

--
Jedaï

[elishac]

Pouvez-vous m'aider à "traduire", dans ce cas ?
En effet, il y a trois choses différentes à traduire, et donc je suis un peu perdu (d'une part, le langage informatique : c'est pas du caml, d'autre part, le langage littéraire : c'est pas du Français, enfin, l'énoncé : les hypothèses sont différentes)...

[SpiceGuid]

Code :

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

1
2
3
4
5
6
type op = Add | Sub | Mul | Div;;
 
type expr =
  | Val of int
  | App of expr * op * expr
  ;;

[Jedai]

Merci SpiceGuid, je suppose que remplacer "data" par "type" c'était trop dur pour lui...

--
Jedaï

[elishac]

Code :

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

1
2
 
type op = Add | Sub | Mul | Div;;

Ne faut-il pas préciser Add of float*float ?
ou alors :
type 'a op= Add of 'a*'a | Sub of 'a*'a | Mul of 'a*'a | Div of 'a*'a;;



Et sinon, vous êtes finalement d'accord avec mon idée de la partition ?

Si oui, qu'est-ce qui ne va pas avec la fonction que j'ai appelé 'formule' dans mon premier message et qui donne tous les abres possibles ?

[Jedai]

Add of 'a * 'a ? Et pourquoi donc ? Réexamine au moins ce que tu fais, le type de ta fonction eval par exemple !

Ta fonction partition a l'air correcte, bien qu'affreusement laide. Sur le même principe, j'écrirais plutôt en Haskell :

Code Haskell :

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

1
2
3
4
5
powerset []     = [[]]
powerset (x:xs) = xss ++ map (x:) xss
  where xss = powerset xs
 
cuts xs = map (id &&& (xs \\)) $ powerset xs

Et tu pourrais faire à peu près la même chose en OCaml, quelque chose comme ça :

Code OCaml :

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

1
2
3
4
5
6
7
8
open List
let rec powerset = function
   | [] -> [[]]
   | (x::xs) -> let xss = powerset xs in xss @ (map (fun xs -> x::xs) xss)
;;
 
let cuts xs = map (fun ys -> partition (fun x -> mem x ys) xs) (powerset xs)
;;

(partition est déjà une fonction de List, ce n'est pas une bonne idée d'en reprendre le nom)

Par ailleurs ça serait déjà bien que tu nous présentes quelque chose qui compile plutôt que de nous dire que ta fonction formule (qui ne compile pas) est très bien.

--
Jedaï

[elishac]

Justement, je ne comprends pas pourquoi ma fonction formule ne marche pas, c'est bien là mon problème. Quelqu'un peut-il m'aider à la corriger ?

[Jedai]

Justement, je ne comprends pas pourquoi ma fonction formule ne marche pas, c'est bien là mon problème. Quelqu'un peut-il m'aider à la corriger ?

Comment veux-tu qu'on t'aide à la corriger alors qu'elle est incompréhensible !! Pour ma part je n'ai pas envie de faire l'effort d'essayer de deviner ce que tu avais à l'esprit quand tu as écris ça !!

Je peux au moins te dire quelques uns des points qui me choquent :

Code :

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

let rec formule f lc = match F with

Tu peux me dire d'où vient ce "F", le paramètre de ta fonction s'appelle "f" que je sache ?

Code :

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

1
2
3
 |[x] ->[x] 
 |_-> 
  let rec f (partie_fixe, lc, partie_variant) = match partie_variant with

Donc tu avais un paramètre qui s'appelait "f" et tu crée une fonction interne qui s'appelle aussi "f", excellente idée, vraiment !

Code :

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

1
2
3
 
   |[x] ->[x] 
   | triplet1 ::q->(partie_fixe, lc, triplet1) :: (f (partie_fixe, lc, q))

Ici il ne s'agit que de devinette, mais tu sembles donner un type bizarre à f : je ne sais pas s'il renvoie une liste de 'a ou de (*,*,'a) ('a étant le type des éléments de la liste partie_variant). En bref f est mal typée.

Code :

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

1
2
3
4
 
  let rec pour_chaque_partition=function
   |[ ]->[ ]
   |couple1 :: q-> let couple1 = (partie1,partie2) in

Visiblement tu voulais écrire "let (partie1,partie2) = couple1" parce que là ça n'a aucun sens...tu redéfinis couple1 à partir de variables pas encore initialisées.

Code :

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

(f partie1 (f partie2 partie1)) @ (pour_chaque_partition q)

Aux dernières nouvelles, f était une fonction à un seul argument... sauf que là tu l'utilises avec 2 arguments.

Code :

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

pour_chaque_partition (partition f);;

Presque cohérent sauf que "f" n'est plus le paramètre "f" (qui est censé être une liste) mais la fonction interne "f", donc encore une erreur de typage.

Comment veux-tu donc qu'on "corrige" un bordel pareil !

--
Jedaï

[SpiceGuid]

Ne faut-il pas préciser Add of float*float ?
ou alors :
type 'a op= Add of 'a*'a | Sub of 'a*'a | Mul of 'a*'a | Div of 'a*'a;;

Pourquoi un type polymorphe alors que ce dont tu as besoin c'est d'un type récursif ?

Et sinon, vous êtes finalement d'accord avec mon idée de la partition ?

Oui mais tu dois la réécrire pour obtenir le même résultat que la fonction split dans le pdf.

Si oui, qu'est-ce qui ne va pas avec la fonction que j'ai appelé 'formule' dans mon premier message et qui donne tous les arbres possibles ?

Sans un type récursif il est impossible que ta fonction construise un seul arbre. Inutile de la lire ou de la commenter. Ecris le bon type et écris une fonction eval qui compile.

[elishac]

lol ! Effectivement il semble y avoir quelques erreurs !! ...

Mais je débute tout juste, c'est ma première année en informatique, ne soyez pas trop durs avec moi.

Je vais essayer de réfléchir et de corriger les erreurs que tu m'as indiquées, j'enverrai les améliorations dans quelques heures.