Combinatoire à vot bon coeur

par **Valentin03** » 30 Oct 2016, 22:26

Bonjour,
Quelqu'un aurait-il une formule pour savoir combien il y a de combinaisons des six signes: + - * / ( )
Sur une plage de N places toutes occupées
Signes considérés égaux avec répétitions
J'ai cherché ici avec "combinatoire" mais c'est un peu trop planant pour moi
Avec espoir et remerciements pour une explication/nommage des choses.

par **Ben314** » 30 Oct 2016, 23:13

Salut,
Je comprend pas grand chose....
En particulier, bien qu'ayant lu 3 fois la phrase "Signes considérés égaux avec répétitions" j'ai bien du mal à en percevoir le sens.

Tu pourrais pas nous la refaire en bon vieux Français par hasard ?
Et/Ou nous donner la liste de ce que tu compte dénombrer lorsque par exemple N=2 ou N=3 ?

par **Valentin03** » 30 Oct 2016, 23:30

J'ai le projet de faire un logiciel qui d'une formule quelconque à quatre signes et parenthèses, donnera toutes les égalités
Mais je voudrais savoir à quelle longueur de formule (N signes) il faut raisonnablement se limiter, vu qu'il doit y avoir de la factorielle en embuscade
Pour simplifier on considère les parenthèses comme des signes (d'où les "signes égaux")
Comme dans toute formule, les signes peuvent êtres répétés
Si quelqu'un connaît un logiciel open source qui fait ça je suis preneur

par **fatal_error** » 31 Oct 2016, 00:08

le pb des parentheses, cest qu'elles vont par deux.. le plus simple est de considerer la notation polonaise inversée (prefixe ou postfixe) qui fait que du coup tu n'as plus qu à te preoccuper des quatres signes de base

en loccurrence 4^n a supposer que tu aies n+1 nombres

ps: cest ce quavait utilisé leJeu pour resoudre le jeu du compte est bon. pe le code est il encore sur le forum...

par **Valentin03** » 31 Oct 2016, 10:19

fatal_error, pense-tu qu'un logiciel qui d'une formule quelconque à quatre signes et parenthèses, donnerait toutes les égalités soit raisonnablement "faisable" et quelle longueur de formule te paraît limite ?
Merci.

par **fatal_error** » 31 Oct 2016, 14:17

ben à moins qu'on se soit pas compris, le pb est trivial et faisable en une 30aine de minutes.
De mémoire ca commencait à prendre qqsecondes pour 7 nombres (pour trouver une seule solution) donc probablement 6 nombres pour explorer toutes les solutions dans la minutes

il ne faut pas oublier qu'il y a les problèmes d'arrondis liés à la division

par **fatal_error** » 31 Oct 2016, 22:12

bon, 1h20 avec lhtml...
https://jsfiddle.net/uy6mmzns/3/

Code: Tout sélectionner: <!DOCTYPE html> <html> <head> <title>Title of the document</title> <script type="text/javascript"> var evaluate={ '+':(a,b)=>a+b, '-':(a,b)=>a-b, '*':(a,b)=>a*b, '/':(a,b)=>{b==0?null:a/b} } var operators = Object.keys(evaluate); //does not touch hand function go(hand, handSize, goal){ if(handSize ==1){ if(hand[0].v == goal){ console.log('GOAL '+hand[0].toString()); } return; } for(var i = 0; i<hand.length; ++i){ for(var j = i+1; j<hand.length; ++j){ var t = hand.slice(0); var a = t.splice(i,1)[0]; var b = t.splice(j-1,1)[0]; operators.forEach(op=>{ var v = evaluate[op](a.v,b.v); if(v!=null){ t[handSize-2] = new Tree(a,b,op,v); go(t, handSize-1, goal); } }) } } } function Tree(a,b,op,v){ this.a = a; this.b = b; this.op = op; this.v = v; } Tree.prototype.toString = function(){ var strongNoPar = function(x){ return x.leaf()?x.v:'('+x.toString()+')'; } var noPar = function(x){ return x.leaf()?x.v: x.multiplicative()?x.toString():'('+x.toString()+')'; } if(this.leaf()){ return this.v; } if(this.op == '+'){ return this.a.toString()+this.op+this.b.toString(); } if(this.op == '-'){ return this.a.toString()+this.op+noPar(this.b); } return noPar(this.a)+this.op+strongNoPar(this.b); } Tree.prototype.leaf = function(){ return !this.a; } Tree.prototype.multiplicative = function(){ if(this.leaf()){return true;} return (this.op=='*' || this.op=='/') && this.a.multiplicative() && this.b.multiplicative(); } function process(f){//'2+3*5-(1+6*50)' var goal = eval(f); var numbers = f.replace(/[()]/g,'').split(/[-+*/]/).map(x=>new Tree(null,null,null,parseFloat(x.trim(), 10))); var bef = Date.now(); go(numbers, numbers.length, goal) console.log('goal was '+ goal+ ', elapsed '+ Math.floor(Date.now()-bef)+' ms') } window.onload = function(){ var junk = document.getElementById('junk'); console.log(document.getElementsByTagName('form')[0]) document.getElementsByTagName('form')[0].onsubmit = function(e){ e.preventDefault(); try{ var tmp = console.log; console.log = function(s){ junk.innerHTML += s+'<br/>'; } process(this.formula.value); console.log = tmp; }catch(e){console.log('moron'+e);} return false; } } </script> </head> <body> <form action="#"> <input type="text" name="formula" value="1+3*(5-1)"/> <input type="submit"/> </form> <hr/> <div id="junk"></div> </body> </html>

note: c'est dommage, on avait déjà fait ca, mais il semblerait que des discussions soient perdues sur le forum (pb lors de la migration à ce forum...)

edit: j'ai vérifié à la va vite, peut être raté mon toString

par **Valentin03** » 01 Nov 2016, 09:11

Merci, je vais étudier ce que tu m'a donné
Dans ma naïveté je considère les parenthèses comme des caractères de chaîne à analyser
Au même titre que les signes, soumises et impliquant des règles, comme les signes
En regardant vite fait je crois comprendre qu'on ne se soucie pas des règles
Qu'il suffit de résoudre les différentes configurations avec des valeurs fixées et de les comparer au résultat chiffré
Ce qui est absolument génial !
(Je comptais faire en algos le cheminement de pensée de la résolution.: Analyse de la formule, choix de stratégies...Ext...Je suis dingue.)
fatal_error, je te bénis

Edit: Et je te remercie
Re Edit: Je subodore que lorsque ça matche, il faut faire une levée de doute avec des valeurs différentes.
Ou un bon résultat ne peut-il venir que d'une bonne formule ?

par **fatal_error** » 01 Nov 2016, 11:30

Je subodore que lorsque ça matche, il faut faire une levée de doute avec des valeurs différentes.
Ou un bon résultat ne peut-il venir que d'une bonne formule ?

je comprends pas trop ta question, alors je vais tartiner en espérant que qqch y réponde...
l'algo grosso est similaire à http://eternitygames.free.fr/LeCompteEstBon.html

1) extraire les nombres de la formule 3+7+2*5 => {3,7,2,5}
2) pour chaque formule générée par {3,7,2,5} regarder si la valeur vaut goal (ici 3+7+2*5=20)
3) si oui afficher le resultat et continuer

2) consiste en:
2: pour ton tableau de n nombres (ici 4 au début) (3,7,2,5)
2.1: tu prendre deux nombres parmi n: n1, et n2 (ex: 2,5, n=={3,7})
2.1.1: pour chaque opération, (+,-,*,/) tu calcules n1 'op' n2 (ex: 2*5=10)
2.1.2: tu mets le resultat dans n: maintenant n=={10,3,7}
2.1.3: tu recommences 2, mais cette fois avec n = {10,3,7}
quand n est de taille 1, tu regardes si goal est atteint (seulement quand n == 1, parce qu'ici j'ai fait l'assertion que ta formule n'est valide QUE si tous les nombres ont été mis en jeu)

comment tracker les opérations?
tu pourrais rajouter un paramètre str dans la fonction, et à chaque appel, concaténer l'opération effectuée. Tu pourrais par exemple afficher:
3+7=10
2*5=10
10+10=20
goal

mais comme toi tu veux des formules le plus simple est de tracker d'où tes résultat viennent, d'ou le stockage sous forme d'arbre (tu as d'autre forme de stockage plus efficaces mais flemme)
ici on store donc
(3),(7),(2),(5) (des feuilles)
puis (10, '+', (3),(7)),(2),(5) (où (10, '+', (3),(7)) représente un arbre de fils gauche (3) et de fils droit (7)
puis (10, '+', (3),(7)),(10, '*', (2),(5))
puis (20, '+', (10, '+', (3),(7)),(10, '*', (2),(5))) (ici, n == 1, on regarde si l'arbre vaut goal==20, c'est le cas, on l'affiche)

enfin, il n'y a plus qu'à retrouver la formule à partir de ton arbre

donc qqsoit le résultat quand n==1 il vient d'une "bonne" formule, dans le sens ou la formule est correcte (sauf erreur d'implémentation), mais le résultat ne vaut pas forcément goal. C'est un brute force, on tente toutes les formules et on affiche que celles dont l'évaluation vaut goal

par **Ben314** » 01 Nov 2016, 12:25

(re)salut.
Je continue à regarder en diagonale ce thread, mais j'ai toujours absolument rien compris à ce que demandais l'auteur avec ces "Signes considérés égaux avec répétitions" ou "...qui d'une formule quelconque à quatre signes et parenthèses, donnera toutes les égalités" et autre "on considère les parenthèses comme des signes".
Si y'a quelqu'un (par exemple fatal_error...) qui a compris quoi que ce soit à ce charabia, il pourrait pas en faire une traduction en Français, histoire que je meure pas idiot ?

par **fatal_error** » 01 Nov 2016, 15:31

salut ben,

Code: Tout sélectionner: J'ai le projet de faire un logiciel qui d'une formule quelconque à quatre signes et parenthèses, donnera toutes les égalités

comprendre, la formule est une expression (mettant en jeu les 4 symboles opératoires +,*,-,/, ainsi que la priorité via le parenthèsage).
De ce que je comprends valentin03 veut l'ensemble des expressions mettant en jeu (une et une seule fois chacun des) nombres de départ, en réarrangeant les nombres et choisissant les opérateurs au bon vouloir, Ces expressions ne sont satisfaisantes QUE si en les évaluant, on trouve la même valeur que celle de base.

ex: avec 3 nombres, a,b,c et les opérations + et * on peut générer
abc
acb
bac
bca
cab
cba
puis en interposant les opérateurs au bon vouloir
a+b+c, a*b+c, a*b*c, a+b*c (pour le premier triplet)
etc...

si de base nous avions eu l'expression 3+4*1
une solution triviale serait 3*1+4, mais 1*3+4, 3+1*4 sont également les "égalités" (ou expressions équivalentes) dont parle valentin03

plusieurs fois je me suis toujours demandé comment représenter ce pb en plein de kernels pour openCl (idem massivement parallèle, avec contraintes de mémoire disponible) mais je manque de connaissances (sur la plateforme) et les méthodes de décomposition, alors je m'évade... mais ca serait une approche intéressante au pb)

par **Valentin03** » 01 Nov 2016, 16:07

Pour résumer, ce que je veux faire, c'est:
A partir de: x=a+b*(c-a); faire passer tour à tour a, b et c à gauche du signe égale en tant qu'inconnues
x, étant connu par la résolution de la première formule, expression
Il devient paramètre ("d"); pendant que a, b et c prenent tour à tour la place de x
Bref, tirer toutes les égalités ou expressions équivalentes possibles.
Fatal_error, tes explications sont un vrai plaisir, encore merci.

Edit: Et les liens sont supers, j'ai de quoi ronger, je suis comblé

par **Ben314** » 01 Nov 2016, 16:36

Déjà, en regardant ce que Fatal à écrit, puis ce que Valentin a écrit, ça me donne un tout petit peu l'impression que j'était pas le seul à pas avoir compris un traitre mot du charabia de départ...

Sinon, Valentin, c'est quoi que tu appelle "faire passer" dans ton expression "faire passer tour à tour a, b et c à gauche du signe égal".
Parce que moi, je suis mathématicien (et pas magicien...) et j'ai jamais rien "fait passer" dans un équation : je sais multiplier/diviser/ajouter/soustraire la même chose aux deux membres, mais c'est tout ce que je sais faire.

Par exemple, si au départ x=a-a, tu fait comment pour "faire passer le a à gauche du égal" ?
Et si x=a*a*a*a*a+a+1, tu fait comment pour "faire passer a de l'autre coté" ?

par **Valentin03** » 01 Nov 2016, 22:08

Ben314 a écrit:Par exemple, si au départ x=a-a, tu fait comment pour "faire passer le a à gauche du égal" ?
Et si x=a*a*a*a*a+a+1, tu fait comment pour "faire passer a de l'autre coté" ?

A cas particulier réponse particulière:
Comme a=a; a-a =x; a est bien passé à gauche
Pour: x=a*a*a*a*a+a+1 je ne suis pas assez calé, mais si fatal_error s'en occupe il va bien te sortir a f(x)
Ben, si tu lis en diagonale, c'est normal que tu comprenne de travers (sans vouloir t'offenser)

par **Ben314** » 01 Nov 2016, 22:31

Valentin03 a écrit:A partir de : x=a+b*(c-a) . . .
pendant que a, b et c prennent tour à tour la place de x

Valentin03 a écrit:a-a =...; a est bien passé à gauche

Il faudra (de nouveau) que tu m'explique la signification de l'expression "prendre la place de" vu que, perso, partant de x=a-a, j'aurais pas vraiment dit que a pouvait "prendre la place" de quoi que ce soit...

Valentin03 a écrit:Pour: x=a*a*a*a*a+a+1 je ne suis pas assez calé, mais si fatal_error s'en occupe il va bien te sortir a f(x)

J'attends avec une grand impatience que fatal_error règle ce "petit détail" (*)

Valentin03 a écrit:Ben, si tu lis en diagonale, c'est normal que tu comprenne de travers (sans vouloir t'offenser)

Oui, c'est vrai que fatal-error, qui lui a tout lu pas en diagonale du tout, ça donne tout à fait l'impression que, dans ces posts précédents, il a répondu a la question posé dans ton post du 01 Nov 2016 15:07
J'attends (de nouveau avec impatience) de voir ce que l'intéresse (fatal-error) dira concernant la pertinence des réponses qu'il a donnés par rapport à la question du post en question.

(*) Si un jour tu fait un minimum de math., tu comprendra pourquoi c'est de l'humour...

par **fatal_error** » 01 Nov 2016, 23:15

Code: Tout sélectionner: J'attends avec une grand impatience que fatal_error règle ce "petit détail" (*)

compte tenu du fait que a-a=x, a est bien passé à gauche,
a*a*a*a*a+a = x-1, a est également bien passé à gauche!

Code: Tout sélectionner: J'attends avec une grand impatience que fatal_error règle ce "petit détail" (*)

je sais pas à qui s'addresse l'humour, mais je passe, la page wiki de galois me calme et la dette de la connaissance s'accumule : (

Concernant la pertinence de mes réponses, je ne vois pas en quoi ajouter qu'elles étaient à côté t'apportera quoique ce soit?

par **Ben314** » 01 Nov 2016, 23:25

@fatal_error : j'avais pas fait gaffe qu'il y avait un thread concernant la résolution du "compte est bon" (ça devait être à une époque où je foutais plus les pieds sur le forum).
Il y a quelques années, j'avais fait un programme de résolution (en C, mais tapé à la cochon comme tout ce que je tape) en essayant d'éviter le plus possible toute forme de redondance dans les calculs, du style calculer A+B puis plus tard lui ajouter C lors d'une "descente" et, lors d'une autre "descente" commencer par calculer A+C pour ensuite lui ajouter B.
L'idée c'était, partant d'un certain nombre N de plaques, de les scinder en M<N paquets (paquet contenant éventuellement un seul élément) puis de remplacer chaque "paquet" par la somme de certains termes du paquet moins la somme des autres (en envisageant bien sûr tout les cas de figure).
Ensuite, partant des M résultats obtenus, on recommence exactement la même chose (faire des "paquets) mais en remplaçant les addition/soustration par des multiplications/divisions.
Puis on recommence de nouveau avec des additions/soustractions, mais en ne faisant aucun "paquet" de plus d'un élément ne contenant que des trucs qui n'ont pas été modifiés par la "mise en paquet multiplicative" précédente vu que de tels paquets aurait déjà pu être fait lors de la première "mise en paquet additive".
etc etc...
Mon objectif était (un peu) de diminuer le temps de calcul, mais surtout de voir jusqu'à quel point j'arriverais à faire un algo. qui ne proposerais que des solutions réellement différentes et pas des trucs du style 95=(25+75)-(3+2) puis 95=(25-3)+(75-2)

par **Ben314** » 01 Nov 2016, 23:40

fatal_error a écrit:compte tenu du fait que a-a=x, a est bien passé à gauche,
a*a*a*a*a+a = x-1, a est également bien passé à gauche!

C'est pas con comme méthode : avec ce point de vue concernant ce qu'est un "passage à gauche", on doit effectivement y arriver assez souvent.
Par exemple, partant du x=a+b*(c-a) de valentin, je propose comme "passage du 'a' à gauche" d'écrire a+b*(c-a)=x.

Sinon, j'espère que tu aura compris que dans mon avant dernier post., ce n'est absolument pas toi que je "vise" : ça m'est arrivé un grand nombre de fois de répondre complètement à coté de la plaque lorsque l'énoncé est un vrai charabia.
Le truc, c'est que je suis de plus en plus un vieux c..., que ça m'énerve de plus en plus de voir la quantité de monde qui, sans parler d'arriver à résoudre un problème, n'arrive même pas à formuler une question de façon intelligible.
Et là, de voir que Valentin03, non seulement il est pas foutu de poser une question de façon compréhensible, mais qu'en plus il n'est même pas foutu de comprendre que ce qu'on lui répond n'a rien à voir avec la question qu'il se pose, on va dire que ça m'a un peu "fait sortir de mes gonds"....

par **fatal_error** » 02 Nov 2016, 08:37

Code: Tout sélectionner: Mon objectif était (un peu) de diminuer le temps de calcul

en fait je sais pas si sur un cpu ca réduit drastiquement le temps de calcul, mais comme ca fait très dynamique, je pense que sur gpu ca peut être pas mal. Je vais essayer de me sortir les doigts pour tester les deux approches..

concernant l'"unicité" des solutions, je me rappèle les avoir gérées à posteriori (en éliminant les doublons): en triant les arbres (en prenant root, puis en remontant tous les arbres additifs à niveau de root, puis en les triant, puis dans chaque noeud multiplicatif idem), mais je crois que leJeu les traitait en plein cours dans son algo (malheureusement je crois que la discussion a été perdue, je ne la retrouve plus

)

en terme de perfs il me semble que les approches étaient équivalentes en temps, mais bon...les benchmarks ont été perdus grr

par **Valentin03** » 02 Nov 2016, 10:40

Désolé de te désoler ben, mais avant de savoir, on ne sait pas.

Cite: "mais qu'en plus il n'est même pas foutu de comprendre que ce qu'on lui répond n'a rien à voir avec la question qu'il se pose"
Comment peux-tu affirmer cela alors que tu avoue ne pas avoir compris la question ?

fatal_error n'a pas répondu à ma question, mais comme il a lu ce que je voulais, il a donné un tas de tuyaux qui répondent parfaitement à ma question.
Et là où il a fait fort, c'est qu'il ne s'est pas laissé embarqué par la question qui faisait référence aux règles (et au raisonnement) et où il m'aurait perdu; il a donné une autre façon de faire (brute force).Que je trouve absolument réjouissante, et qui n'est absolument pas mathématique.

Cite: "je propose comme "passage du 'a' à gauche" d'écrire a+b*(c-a)=x."
"Tour à tour à gauche", ça veut dire "a" tout seul à gauche, puis "b" tout seul à gauche ...ext.
Etant entendu que ce qui est à gauche, c'est ce qu'on cherche, si tu mets x à droite, tu peux calculer jusqu'à la fin des temps.

Je conçois qu'en tant que matheux, "x" soit pour toi l'immuable inconnue.
Pour moi, "x" est un état comme dans: "a devient x; et x devient "d"

La vitesse c'est bien, mais pendant que le cpu tourne, on peut penser ou rêver

Combinatoire à vot bon coeur

Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Re: Combinatoire à vot bon coeur

Qui est en ligne