Génération d'une expression mathématique aléatoire

16

J'ai cette idée qui court dans ma tête, pour générer et évaluer des expressions mathématiques aléatoires. J'ai donc décidé de lui donner un coup de feu et d'élaborer un algorithme, avant de le coder pour le tester.

Exemple:

Voici quelques exemples d'expressions que je souhaite générer de manière aléatoire:

4 + 2                           [easy]
3 * 6 - 7 + 2                   [medium]
6 * 2 + (5 - 3) * 3 - 8         [hard]
(3 + 4) + 7 * 2 - 1 - 9         [hard]
5 - 2 + 4 * (8 - (5 + 1)) + 9   [harder]
(8 - 1 + 3) * 6 - ((3 + 7) * 2) [harder]

Les plus faciles et les moyens sont assez simples. Les aléatoires intsont séparés par des opérateurs aléatoires, rien de fou ici. Mais j'ai du mal à démarrer avec quelque chose qui pourrait créer l'un des exemples les plus difficiles et les plus difficiles . Je ne suis même pas sûr qu'un seul algorithme puisse me donner les deux derniers.

Ce que j'envisage:

Je ne peux pas dire que j'ai essayé ces idées, car je ne voulais pas vraiment perdre beaucoup de temps à aller dans une direction qui n'avait aucune chance de travailler en premier lieu. Mais quand même, j'ai pensé à quelques solutions:

  • Utiliser des arbres
  • Utilisation d'expressions régulières
  • Utiliser une folle boucle "for-type" (sûrement la pire)

Ce que je cherche:

Je voudrais savoir quelle est, selon vous, la meilleure solution, entre les solutions que j'ai envisagées et vos propres idées.

Si vous voyez une bonne façon de commencer, j'apprécierais une avance dans la bonne direction, par exemple avec le début de l'algorithme, ou une structure générale de celui-ci.

Notez également que je devrai évaluer ces expressions. Cela peut être fait soit après la génération de l'expression, soit lors de sa création. Si vous prenez cela en considération dans votre réponse, c'est parfait.

Je ne recherche rien de lié à la langue, mais pour mémoire, je pense à l'implémenter dans Objective-C, car c'est la langue avec laquelle je travaille le plus récemment.

Ces exemples n'incluaient pas l' :opérateur, car je veux seulement manipuler ints, et cet opérateur ajoute de nombreuses vérifications. Si votre réponse donne une solution pour gérer celle-ci, c'est parfait.

Si ma question nécessite des éclaircissements, veuillez la poser dans les commentaires. Merci de votre aide.

rdurand
la source
2
hmmm, ajoutez une fonction fitness et il semble que vous vous dirigiez vers la programmation génétique .
Philip

Réponses:

19

Voici une interprétation théorique de votre problème.

Vous cherchez à générer de manière aléatoire des mots (expression algébrique) à partir d'une langue donnée (l'ensemble infini de toutes les expressions algébriques syntaxiquement correctes). Voici une description formelle d'une grammaire algébrique simplifiée prenant uniquement en charge l'addition et la multiplication:

E -> I 
E -> (E '+' E)
E -> (E '*' E)

Ici, Eest une expression (c'est-à-dire un mot de votre langue) et Iest un symbole terminal (c'est-à-dire qu'il n'est plus développé) représentant un entier. La définition ci-dessus pour Ea trois règles de production . Sur la base de cette définition, nous pouvons construire au hasard une arithmétique valide comme suit:

  1. Commencez avec Ecomme symbole unique du mot de sortie.
  2. Choisissez uniformément au hasard l'un des symboles non terminaux.
  3. Choisissez uniformément au hasard l'une des règles de production de ce symbole et appliquez-la.
  4. Répétez les étapes 2 à 4 jusqu'à ce qu'il ne reste que des symboles de terminal.
  5. Remplacez tous les symboles terminaux Ipar des nombres entiers aléatoires.

Voici un exemple de l'application de ces algorithmes:

E
(E + E)
(E + (E * E))
(E + (I * E))
((E + E) + (I * E))
((I + E) + (I * E))
((I + E) + (I * I))
((I + (E * E)) + (I * I))
((I + (E * I)) + (I * I))
((I + (I * I)) + (I * I))
((2 + (5 * 1)) + (7 * 4))

Je suppose que vous choisiriez de représenter une expression avec une interface Expressionimplémentée par les classes IntExpression, AddExpressionet MultiplyExpression. Les deux derniers auraient alors un leftExpressionet rightExpression. Toutes les Expressionsous-classes sont nécessaires pour implémenter une evaluateméthode qui fonctionne récursivement sur la structure arborescente définie par ces objets et implémente efficacement le modèle composite .

Notez que pour la grammaire et l'algorithme ci-dessus, la probabilité de développer une expression Edans un symbole terminal Iest seulement p = 1/3, tandis que la probabilité de développer une expression dans deux autres expressions est 1-p = 2/3. Par conséquent, le nombre attendu d'entiers dans une formule produite par l'algorithme ci-dessus est en fait infini. La longueur attendue d'une expression est soumise à la relation de récurrence

l(0) = 1
l(n) = p * l(n-1) + (1-p) * (l(n-1) + 1)
     = l(n-1) + (1-p)

l(n)dénote la longueur attendue de l'expression arithmétique après napplication des règles de production. Je suggère donc que vous affectiez une probabilité assez élevée pà la règle de E -> Isorte que vous vous retrouvez avec une expression assez petite avec une probabilité élevée.

EDIT : Si vous craignez que la grammaire ci-dessus produise trop de parenthèses, regardez la réponse de Sebastian Negraszus , dont la grammaire évite ce problème très élégamment.

blubb
la source
Whoa .. C'est super, j'aime beaucoup ça, merci! Je dois encore approfondir un peu toutes les solutions proposées pour faire le bon choix. Merci encore, excellente réponse.
rdurand
Merci pour votre montage, c'est une chose à laquelle je n'ai pas pensé. Pensez-vous que limiter le nombre de fois que vous passez par les étapes 2 à 4 pourrait fonctionner? Disons, après 4 (ou autre) itérations des étapes 2 à 4, n'autoriser que la règle E-> I ?
rdurand
1
@rdurand: Oui, bien sûr. Disons qu'après des mitérations de 2 à 4, vous «ignorez» les règles de production récursives. Cela conduira à une expression de la taille attendue l(m). Notez cependant que cela n'est (théoriquement) pas nécessaire, car la probabilité de générer une expression infinie est nulle, même si la taille attendue est infinie. Cependant, votre approche est favorable car dans la pratique, la mémoire n'est pas seulement finie, mais aussi petite :)
blubb
Avec votre solution, je ne vois pas comment résoudre l'expression en la construisant. Y a-t-il ? Je peux toujours le résoudre par la suite, mais je préfère ne pas.
rdurand
Si vous le souhaitez, pourquoi ne pas commencer par un nombre aléatoire comme expression de base et le décomposer au hasard (le réécrire) en opérations, de la manière décrite par blubb? Ensuite, non seulement vous auriez la solution pour l'expression entière, mais vous obtiendriez également facilement des sous-solutions pour chacune des branches de l'arbre d'expression.
mikołak
7

tout d'abord, je générerais l'expression en notation postfixe , vous pouvez facilement convertir en infixe ou évaluer après avoir généré votre expression aléatoire, mais le faire en postfix signifie que vous n'avez pas à vous soucier des parenthèses ou de la priorité.

Je garderais également un total cumulé du nombre de termes disponibles pour l'opérateur suivant dans votre expression (en supposant que vous vouliez éviter de générer des expressions mal formées), c'est-à-dire quelque chose comme ceci:

string postfixExpression =""
int termsCount = 0;
while(weWantMoreTerms)
{
    if (termsCount>= 2)
    {
         var next = RandomNumberOrOperator();
         postfixExpression.Append(next);
         if(IsNumber(next)) { termsCount++;}
         else { termsCount--;}
    }
    else
    {
       postfixExpression.Append(RandomNumber);
       termsCount++;
     }
}

évidemment c'est du pseudo code donc il n'est pas testé / peut contenir des erreurs et vous n'utiliseriez probablement pas une chaîne mais une pile d'union comme le type

jk.
la source
cela suppose actuellement que tous les opérateurs sont binaires, mais son assez facile à étendre avec des opérateurs de différentes arités
jk.
Merci beaucoup. Je n'ai pas pensé à RPN, c'est une bonne idée. J'examinerai toutes les réponses avant d'en accepter une, mais je pense que je pourrais faire en sorte que cela fonctionne.
rdurand
+1 pour le post-fix. Vous pouvez éliminer le besoin d'utiliser autre chose qu'une pile, ce qui, à mon avis, est plus simple que de construire un arbre.
Neil
2
@rdurand Une partie de l'avantage du post-fix signifie que vous n'avez pas à vous soucier de la priorité (qui a déjà été prise en compte avant de l'ajouter à la pile post-fix). Après quoi, vous sautez simplement tous les opérandes que vous trouvez jusqu'à ce que vous sautiez le premier opérateur que vous trouvez sur la pile, puis vous poussez sur la pile le résultat et vous continuez de cette manière jusqu'à ce que vous sortiez la dernière valeur de la pile.
Neil
1
@rdurand L'expression 2+4*6-3+7est convertie en pile post-correction + 7 - 3 + 2 * 4 6(le haut de la pile étant le plus à droite). Vous poussez 4 et 6 et appliquez l'opérateur *, puis vous repoussez 24. Vous sautez ensuite 24 et 2 et appliquez l'opérateur +, puis vous repoussez 26. Vous continuez de cette manière et vous constaterez que vous obtiendrez la bonne réponse. Notez que ce * 4 6sont les premiers termes de la pile. Cela signifie qu'elle est effectuée en premier parce que vous avez déjà déterminé la priorité sans nécessiter de parenthèses.
Neil
4

La réponse de blubb est un bon début, mais sa grammaire formelle crée trop de paranthèses.

Voici mon point de vue:

E -> I
E -> M '*' M
E -> E '+' E
M -> I
M -> M '*' M
M -> '(' E '+' E ')'

Eest une expression, Iun entier et Mest une expression qui est un argument pour une opération de multiplication.

Sebastian Negraszus
la source
1
Belle extension, celle-ci a certainement l'air moins encombrée!
blubb
Comme j'ai commenté la réponse de blubb, je garderai des parenthèses indésirables. Peut-être faire le hasard "moins aléatoire";) merci pour le module complémentaire!
rdurand
3

Les parenthèses dans l'expression "dure" représentent l'ordre d'évaluation. Plutôt que d'essayer de générer directement le formulaire affiché, il vous suffit de dresser une liste d'opérateurs dans un ordre aléatoire et d'en dériver la forme d'affichage.

Nombres: 1 3 3 9 7 2

Les opérateurs: + * / + *

Résultat: ((1 + 3) * 3 / 9 + 7) * 2

Dériver la forme d'affichage est un algorithme récursif relativement simple.

Mise à jour: voici un algorithme en Perl pour générer le formulaire d'affichage. Parce que +et *sont distributifs, il randomise l'ordre des termes pour ces opérateurs. Cela aide à empêcher les parenthèses de s'accumuler d'un côté.

use warnings;
use strict;

sub build_expression
{
    my ($num,$op) = @_;

    #Start with the final term.
    my $last_num = pop @$num; 
    my $last_op = pop @$op;

    #Base case: return the number if there is just a number 
    return $last_num unless defined $last_op;

    #Recursively call for the expression minus the final term.
    my $rest = build_expression($num,$op); 

    #Add parentheses if there is a bare + or - and this term is * or /
    $rest = "($rest)" if ($rest =~ /[+-][^)]+$|^[^)]+[+-]/ and $last_op !~ /[+-]/);

    #Return the two components in a random order for + or *.
    return $last_op =~ m|[-/]| || rand(2) >= 1 ? 
        "$rest $last_op $last_num" : "$last_num $last_op $rest";        
}

my @numbers   = qw/1 3 4 3 9 7 2 1 10/;
my @operators = qw|+ + * / + * * +|;

print build_expression([@numbers],[@operators]) , "\n";

la source
Cet algorithme semble toujours générer des arbres déséquilibrés: la branche gauche est profonde, tandis que celle de droite n'est qu'un seul nombre. Il y aurait trop de parans d'ouverture au début de chaque expression, et l'ordre des opérations est toujours de gauche à droite.
scriptin
Merci pour votre réponse, dan, ça aide. Mais @scriptin, je ne comprends pas ce que vous n'aimez pas dans cette réponse? Pourriez-vous expliquer un peu?
rdurand
@scriptin, qui peut être corrigé avec une simple randomisation de l'ordre d'affichage. Voir la mise à jour.
@rdurand @ dan1111 J'ai essayé le script. Le problème du grand sous-arbre gauche est résolu, mais l'arbre généré est toujours très déséquilibré. Cette image montre ce que je veux dire. Cela peut ne pas être considéré comme un problème, mais cela conduit à une situation où des sous-expressions comme ne(A + B) * (C + D) sont jamais présentées dans les expressions générées, et il y a aussi beaucoup de parens imbriqués.
scriptin
3
@scriptin, après y avoir réfléchi, je suis d'accord que c'est un problème.
2

Pour développer l'approche arborescente, disons que chaque nœud est soit une feuille soit une expression binaire:

Node := Leaf | Node Operator Node

Notez qu'une feuille n'est ici qu'un entier généré de manière aléatoire.

Maintenant, nous pouvons générer au hasard un arbre. Décider de la probabilité que chaque nœud soit une feuille nous permet de contrôler la profondeur attendue, bien que vous souhaitiez également une profondeur maximale absolue:

Node random_tree(leaf_prob, max_depth)
    if (max_depth == 0 || random() > leaf_prob)
        return random_leaf()

    LHS = random_tree(leaf_prob, max_depth-1)
    RHS = random_tree(leaf_prob, max_depth-1)
    return Node(LHS, RHS, random_operator())

Ensuite, la règle la plus simple pour imprimer l'arborescence est d'enrouler ()autour de chaque expression non-feuille et d'éviter de se soucier de la priorité de l'opérateur.


Par exemple, si je mets entre parenthèses votre dernier exemple d'expression:

(8 - 1 + 3) * 6 - ((3 + 7) * 2)
((((8 - 1) + 3) * 6) - ((3 + 7) * 2))

vous pouvez lire l'arbre qui le générerait:

                    SUB
                  /      \
               MUL        MUL
             /     6     /   2
          ADD          ADD
         /   3        3   7
       SUB
      8   1
Inutile
la source
1

J'utiliserais des arbres. Ils peuvent vous donner un grand contrôle sur la génération des expressions. Par exemple, vous pouvez limiter la profondeur par branche et la largeur de chaque niveau séparément. La génération basée sur un arbre donne également la réponse déjà pendant la génération, ce qui est utile si vous voulez vous assurer que le résultat (et les sous-résultats) sont également assez difficiles et / ou pas trop difficiles à résoudre. Surtout si vous ajoutez un opérateur de division à un moment donné, vous pouvez générer des expressions évaluées en nombres entiers.

msell
la source
Merci pour votre réponse. J'ai eu la même idée des arbres, pouvoir évaluer / vérifier les sous-expressions. Peut-être pourriez-vous donner un tout petit peu plus de détails sur votre solution? Comment voulez - vous construire arbre un (pas comment vraiment, mais qu'est - ce que la structure générale être)?
rdurand
1

Voici une interprétation légèrement différente de l'excellente réponse de Blubb:

Ce que vous essayez de construire ici est essentiellement un analyseur qui fonctionne à l'envers. Ce que votre problème et un analyseur ont en commun, c'est une grammaire sans contexte , celle-ci sous la forme Backus-Naur :

digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
number ::= <digit> | <digit> <number>
op ::= '+' | '-' | '*' | '/'
expr ::= <number> <op> <number> | '(' <expr> ')' | '(' <expr> <op> <expr> ')'

Les analyseurs commencent par un flux de terminaux (des jetons littéraux comme 5ou *) et essaient de les assembler en terminaux non (éléments composés de terminaux et d'autres terminaux non, tels que numberou op). Votre problème commence par des non terminaux et fonctionne à l'envers, en choisissant n'importe quoi entre les symboles "ou" (pipe) au hasard quand on en rencontre et en répétant récursivement le processus jusqu'à atteindre un terminal.

Quelques autres réponses ont suggéré qu'il s'agit d'un problème d'arbre, qui l'est pour une certaine classe étroite de cas où il n'y a pas de terminaux non terminaux qui se référencent directement ou indirectement via un autre terminal non terminal. Puisque les grammaires le permettent, ce problème est vraiment un graphe orienté . (Les références indirectes par le biais d'un autre non terminal comptent également pour cela.)

Il y avait un programme appelé Spew publié sur Usenet à la fin des années 1980 qui a été initialement conçu pour générer des titres de tabloïdes aléatoires et s'avère également être un excellent véhicule pour expérimenter ces "grammaires inverses". Il fonctionne en lisant un modèle qui dirige la production d'un flux aléatoire de terminaux. Au-delà de sa valeur d'amusement (titres, chansons country, charabia anglais prononçable), j'ai écrit de nombreux modèles qui sont utiles pour générer des données de test allant du texte brut au XML au C. syntaxiquement correct mais non compilable malgré son âge de 26 ans. et écrit en K&R C et ayant un format de modèle laid, il compile très bien et fonctionne comme annoncé. J'ai préparé un modèle qui résout votre problème et l'ai publié sur pastebin car ajouter autant de texte ici ne semble pas approprié.

Blrfl
la source