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.