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.
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_arbres la fonction qui prend en argument l'ensemble E des scalaires et l'ensemble F des lois de compositions internes, 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).
La première étape est donc de lister toutes les possibilités.

(Remarque : j'avais déjà posé cette question il y a quelque temps, mais mon algorithme et ma programmation étaient incorrects, je préfère donc tout reprendre depuis le début, et suis ouvert à toute idée).

Il y a encore une autre contrainte, mais on pourra y réfléchir plus tard (faisons le peu à peu, sinon ça risque de devenir compliqué) : on a le droit de passer par des réels, mais le résultat final doit être entier.

Merci de m'aider à faire liste_des_arbres, dans un premier temps.

[Steki-kun]

Donc si je comprends bien, c'est le problème des chiffres dans "les Chiffres et les Lettres" mais avec des réels et pour faire un résultat entier c'est bien ça ? :-)

Edit: (question subsidiaire) qu'appelles-tu des "doublons" exactement ? Est-ce que c'est n'importe quelle paire d'arbres qui donne le même résultat ? Ou est-ce que ce sont les arbres qui représentent le "même calcul" ? Par exemple "3*(2*4)" et "(3*2)*4".

[LLB]

Cadeau ! http://www.google.fr/search?hl=fr&q=...compte+est+bon

[Jedai]

Il y a encore une autre contrainte, mais on pourra y réfléchir plus tard (faisons le peu à peu, sinon ça risque de devenir compliqué) : on a le droit de passer par des réels, mais le résultat final doit être entier.

Plutôt que des réels, tu veux des rationnels, ainsi tes calculs seront exact, tu ne manqueras pas de solutions à cause d'une imprécision dans les calculs et tu n'auras pas à te casser la tête avec des epsilons. En fait tu peux faire tout les calculs avec des rationnels, ça sera le plus simple.

--
Jedaï

[elishac]

Oui ce sont des rationnels si l'on veut (mais je ne sais pas si c'est le plus simple à représenter en CaML, alors que les flottants ça marche bien).


Steki-kun et LLB, ça ressemble un peu à des chiffres et des lettres, mais comme Steki-kun l'a dit, on peut passer par des nombres non entiers.
De plus, contrairement à des chiffres et des lettres, on doit utiliser au moins une fois (et au plus une fois) chaque chiffre (en revanche, on utilise les opérations que l'on souhaite).
La question subsidiaire : Le but est le résultat, même si l'on passe par des arbres. Par conséquent, si deux arbres donnent le même résultat, on ne gardera que l'un des deux (mais bon, ça on le fera dans un deuxième temps, la première étape est déjà de lister tous les abres possibles, sans doute en faisant une permutation des feuilles et en décorant de toutes les manières possibles les noeuds, de manière récursive. Par ailleurs, supprimer les arbres qui donnent le même résultat n'est pas difficile : on crée très facilement de manière récursive une fonction eval qui rend l'évaluation de l'arbre (c'est ici qu'interviendront les réels ou les rationnels), et on ajoute le résultat de l'évaluation à une liste liste_resultat, pour peu que liste_resultat ne contienne pas encore le résultat qu'on s'apprête à ajouter).
En conclusion 3*(2*4) et (3*2)*4 n'est compté qu'une seule fois, si c'est le résultat final (par contre, il me semble très difficile de supprimer ce genre de doublons en plein milieu de l'arbre).
En revanche, dans un second temps, on pourra essayer d'améliorer l'algorithme en faisant un test sur l'opérateur : s'il est commutatif, on ne fera les calculs que sur un sous-arbre (par exemple le sous-arbre gauche), puisque par symétrie le sous-arbre droit sera fait aussi.

Jedai, je ne suis pas sûr que les réels soient durs à traiter en CaML (on utilise des flottants). Mais bon, si tu veux on pourra faire des rationnels.
De toute façon, on ne réfléchira à ça que plus tard, pour la fonction eval que j'ai cité plus haut.

La première étape est de lister tous les arbres possibles avec les contraintes énoncées dans le premier message.

[LLB]

Oui ce sont des rationnels si l'on veut (mais je ne sais pas si c'est le plus simple à représenter en CaML, alors que les flottants ça marche bien).

Utilise le type Num. Il gère parfaitement les rationnels (en précision arbitraire).

Steki-kun et LLB, ça ressemble un peu à des chiffres et des lettres, mais comme Steki-kun l'a dit, on peut passer par des nombres non entiers. De plus, contrairement à des chiffres et des lettres, on doit utiliser au moins une fois (et au plus une fois) chaque chiffre (en revanche, on utilise les opérations que l'on souhaite).

La logique reste la même. C'est un exercice classique, regarde sur le net. Il y a plein d'explications.

[Steki-kun]

Hmm, deux choses : déjà si tu veux juste calculer les résultats possibles tu n'es pas obligé de passer par la génération de tous les arbres (est-ce que pour chaque résultat, tu veux vraiment un calcul permettant de l'obtenir ou pas?).

Aussi, pour enlever les doublons, tu ferais bien de pas garder ça dans une liste mais plutôt dans une Hashtbl, parce que quand tu as n réels différents au départ et k opérations, le nombre d'arbres différents va grossir assez vite (il y a C(n-1) différents arbres binaires à n feuilles, où C(n-1) est le (n-1)ème nombre de Catalan ; il y a n! façons de mettre tes n nombres dans tes n feuilles, et il y a k^(n-1) manière de mettre des opérations sur les noeuds internes de chaque arbre.... => ça fait k^(n-1)*(2n-2)!/(n-1)! arbres différents sauf erreur de ma part, et ça grossit en (4k(n-1)/e)^(n-1) --- fin de la parenthèse mathématique ).

[elishac]

(ouverture de la parenthèse mathématique : je suis d'accord pour ton décompte du nombre d'arbres, et pour ta simplification en k^(n-1)*(2n-2)!/(n-1)! . En revanche, je ne comprends pas ton équivalent (notamment je ne comprends pas où est passée la racine carrée de la formule de Stirling).
fin de la parenthèse mathématique)

Je ne sais pas ce qu'est le type Num, ni Hashtbl, mais je veux bien vous croire qu'ils sont efficaces.
Le type Num n'a pas besoin de m'être expliqué pour l'instant, car il ne servira que dans un deuxième temps (lorsqu'on cherchera à évaluer les arbres, la première étape étant de les former).
Par contre le hashtbl est peut-être important dès maintenant, merci de m'expliquer en quoi ça consiste.
De toute facon, on n'est pas obligé de garder tous les arbres dans une liste.
On les évalue en cours de route (on modifiera dans un second temps le programme pour qu'il fasse cela en cours d'éxecution et pas à la fin), et on ajoute le résultat de l'arbre seulement si le résultat n'est pas déjà présent dans la liste (pour répondre à ta première question, Steki-kun, on peut donc si on veut rendre une liste de couples, où le premier élément est l'entier obtenu et le deuxième est l'arbre (ou plus précisément, l'un des arbres) qui a permis de l'obtenir (ce n'est pas ça qui augmentera beaucoup le temps d'éxecution de l'algorithme, et sa pourrait être utile) (évidemment, on ne va pas chercher à écrire tous les arbres qui ont permis d'avoir le même nombre, ne serait-ce que parce que beaucoup d'arbres seront identiques d'après nos simplifications arithmétiques usuelles (commutativité, associativité...). Par ailleurs, on pourra à la fin chercher à améliorer la complexité en considérant ce genre de choses).

Peut-on à présent commencer à s'intéresser à l'écriture en elle-même de l'algorithme ? (je pense que tout le monde à compris la question à présent).

[Steki-kun]

En effet ce qui m'intéressait était un grand O (ou plutôt un grand Theta) mais pas un équivalent, j''ai donc jarreté le coef multiplicateur du terme dominant, qui devait être 4^(-3/4) ou qque chose comme ça.

En ce qui concerne Hashtbl, c'est le nom du module qui implémente les tables de hachage en OCaml. Si tu ne sais pas ce que c'est, disons pour faire simple que c'est un moyen plus efficace de réaliser une table d'association que de le faire avec une liste de couples (accès en temps constant si tt se passe bien, contre accès en O(taille de la liste)). Je rédige en ce moment un tutoriel sur ces modules mais en attendant je t'encourage à regarder http://fr.wikipedia.org/wiki/Tableau_associatif.

J'ai bien compris que tu ne vas garder tous les arbres, mais seulement tous les résultats différents, et qu'il n'y en aura pas autant que mon dénombrement pourrait laisser croire, mais je fais 2 constats :
1/ s'il y a bcp d'arbres, il y aura quand même un nombre certain de résultats différents (même 10% de tout ça, ça fait beaucoup), d'autant que comparé au problème de la télé, ici toutes les divisions sont correctes (sur les entiers, elles ne le sont que rarement)
2/ c'est surtout que quoi qu'il advienne, le nombre d'arbres c'est aussi le nombre de fois que tu vas faire ta petite recherche dans ton tableau associatif pour savoir s'il faut ajouter ce résultat ou pas, donc ça fera une différence notable in fine si cette recherche se fait en temps constant ou en O(nombre de résultats déjà trouvés)

Pour l'algorithme, que dire de plus que ce qui est dit dans les pages renvoyées par la recherche de LLB ?