1
votes

Prolog: Comment générer des expressions mathématiques simples?

J'ai besoin d'écrire (pas de calculer) tous les états de la liste des nombres qui signifie:

Input:

list_sum([Item], Item).
list_sum([Item1,Item2 | Tail], Total) :-
   list_sum([Item1+Item2|Tail], Total).

Output:

1+2+3
1-2-3
1/2/3
1*2*3
1+2-3
1+2/3
1+2*3
1-2+3
1-2/3
1-2*3
1/2+3
1/2-3
1/2+3
1*2+3
1*2-3
1+2-3

dans le code descendant, affichez simplement 1 + 2 + 3

Comment puis-je les développer dans tous les états?

Numbers: 1,2,3
Operators: +,-,/,*

prolog

2 commentaires

Est-ce que (1 + 2) / 3 est une possibilité, ou 1 / (2-3) ?

Vous devez expliquer: quelles sont les choses que vous affichez en sortie, par exemple "1 + 2-3"? S'agit-il de termes composés, comme + (1, - (2, 3)) ou sont-ils des listes comme [1, +, 2, -, 3] ou sont-ils juste des atomes ou des chaînes?

5 Réponses :

1
votes

Un moyen est

 ?- all_operations([1,2,3], Out), maplist(writeln, Out).
1*2*3
1*2+3
1*2-3
1*2/3
1+2*3
1+2+3
1+2-3
1+2/3
1-2*3
1-2+3
1-2-3
1-2/3
1/2*3
1/2+3
1/2-3
1/2/3
Out = ['1*2*3', '1*2+3', '1*2-3', '1*2/3', '1+2*3', '1+2+3', '1+2-3', '1+2/3', '1-2*3'|...].

Résultat

member_(In, X) :-
    member(X, In).

get_calcul([N], _, Temp, Out) :-
    append(Temp, [N], Out).

get_calcul([N|T], [Op|Top], Temp, Out) :-
    append(Temp, [N, Op], Temp1),
   get_calcul(T, Top, Temp1, Out).

all_operations(In, Out) :-
    % if you have N numbers
    length(In, Len),
    % you need N-1 operators
    LenOps is Len - 1,
    length(LOps, LenOps),
   setof(Op, LOps^Ops^(maplist(member_([+,-,*,/]), LOps),get_calcul(In, LOps, [], Ops), atomic_list_concat(Ops, Op)), Out).

Eh bien, j'ai résolu mon problème, pas le vôtre!

Cela peut être fait:

?- all_operations([1,2,3], Out).
Out = ['1*2+3', '1*2-3', '1*2/3', '1+2*3', '1+2-3', '1+2/3', '1-2*3', '1-2+3', '1-2/3'|...].

Par exemple:

get_calcul([X], _, Temp, Calcul):-
    append(Temp, [X], Calcul).

get_calcul([N|T], [Op|Top], Temp, Out) :-
    append(Temp, [N, Op], Temp1),
   get_calcul(T, Top, Temp1, Out).

all_operations(In, Out) :-
   setof(Op, X^Ops^(permutation([+,-,*,/], X), get_calcul(In, X, [], Ops), atomic_list_concat(Ops, Op)), Out).

2 commentaires

qu'en est-il de ['1 + 2 + 3', '1 * 2 * 3', '1/2/3', '1-2-3'] ??

son ne fonctionne pas plus de 3 éléments? pouvez-vous le développer pour plus d'éléments?

2
votes

Utilisation de DCG avec phrase / 2 en tant que generator :

?- expr(E).
E = 1 ;
E = 2 ;
E =  (1, (+), 1) ;
E =  (1, (+), 2) ;
E =  (2, (+), 1) ;
E =  (2, (+), 2) ;
E =  (1, (*), 1) ;
E =  (1, (*), 2) ;
E =  (2, (*), 1) ;
E =  (2, (*), 2) ;
E =  (1, (+), 1, (+), 1) ;
...
E =  (1, (+), 2, (+), 2, (*), 1) ;
E =  (1, (+), 2, (+), 2, (*), 2) ;
E =  (1, (+), (1, (+), 1), (+), 1) ;
E =  (1, (+), (1, (+), 1), (+), 2) ;
E =  (1, (+), (1, (+), 2), (+), 1) ;
...

Exemple d'exécution:

<expr> ::= <op> <expr> <expr>

expr((E1,Op,E2)) --> operator(Op),expr(E1),expr(E2).

Puisque votre question fonctionne avec list, un moyen de voir DCG comme traitement de liste consiste à utiliser listing / 1 pour le convertir en Prologue standard.

<expr> ::= <expr> <op> <expr>

expr((E1,Op,E2)) --> expr(E1),operator(Op),expr(E2).

qui peut être appelé comme Prologue standard.

?- length(Ls,N).
Ls = [],
N = 0 ;
Ls = [_870],
N = 1 ;
Ls = [_870, _876],
N = 2 ;
Ls = [_870, _876, _882],
N = 3 ;
Ls = [_870, _876, _882, _888],
N = 4 ;
Ls = [_870, _876, _882, _888, _894],
N = 5 ;
Ls = [_870, _876, _882, _888, _894, _900],
N = 6 
...

Une solution étendue utilisant un nombre (1, 2, 3) à n'importe quelle position:

number(1) --> [1].
number(2) --> [2].

operator(+) --> [+].
operator(*) --> [*].

expr(N) --> number(N).
expr((E1,Op,E2)) --> operator(Op),expr(E1),expr(E2).

expr(E) :-
    length(Expr,_),
    phrase(expr(E),Expr).

Exemple d'exécution:

?- expr(E).
E = "1+1+1" ;
E = "1+1+2" ;
E = "1+1+3" ;
E = "1+1-1" ;
E = "1+1-2" ;
E = "1+1-3" ;
...

Pour savoir comment générer avec DCG, consultez cette section Amzi : Génération avec des listes de différences

En commentaire pour une autre réponse, vous avez écrit:

ça ne marche pas plus de 3 éléments? pouvez-vous le développer pour plus d'éléments?

À mesure que le nombre d'éléments augmente, l ' explosion combinatoire augmente également.

Pour limiter l'explosion combinatoire de l'exemple, cela n'utilisera que deux nombres (1,2) et deux opérateurs (+, *), vous pouvez en ajouter plus à votre guise.

number --> [1].
number --> [2].
number --> [3].

operator --> [+].
operator --> [-].
operator --> [*].
operator --> [/].

expr_trinary -->
  number,
  operator,
  number,
  operator,
  number.  

expr(E) :-
    phrase(expr_trinary,Expr_trinary),
    atomics_to_string(Expr_trinary,E).

Notez que cela utilise length / 2 pour approfondissement itératif . Fondamentalement, length / 2 génère une liste de longueur croissante puis phrase / 2 propose des réponses de cette longueur.

?- expr_trinary(E,[]).
E = [1, +, 2, +, 3] ;
E = [1, +, 2, -, 3] ;
E = [1, +, 2, *, 3] ;
E = [1, +, 2, /, 3] ;
E = [1, -, 2, +, 3] ;
E = [1, -, 2, -, 3] ;
E = [1, -, 2, *, 3] ;
E = [1, -, 2, /, 3] ;
E = [1, *, 2, +, 3] ;
E = [1, *, 2, -, 3] ;
E = [1, *, 2, *, 3] ;
E = [1, *, 2, /, 3] ;
E = [1, /, 2, +, 3] ;
E = [1, /, 2, -, 3] ;
E = [1, /, 2, *, 3] ;
E = [1, /, 2, /, 3].

Pour que le générateur fonctionne comme prévu, le BNF et DCG, par exemple

?- listing(operator).
operator([+|A], A).
operator([-|A], A).
operator([*|A], A).
operator([/|A], A).

true.

?- listing(expr_trinary).
expr_trinary([1|A], B) :-
    operator(A, C),
    C=[2|D],
    operator(D, E),
    E=[3|B].

true.

qui est récursif gauche direct est converti en ceci

?- expr(E).
E = "1+2+3" ;
E = "1+2-3" ;
E = "1+2*3" ;
E = "1+2/3" ;
E = "1-2+3" ;
E = "1-2-3" ;
E = "1-2*3" ;
E = "1-2/3" ;
E = "1*2+3" ;
E = "1*2-3" ;
E = "1*2*3" ;
E = "1*2/3" ;
E = "1/2+3" ;
E = "1/2-3" ;
E = "1/2*3" ;
E = "1/2/3".

Exemple d'exécution:

operator --> [+].
operator --> [-].
operator --> [*].
operator --> [/].

expr_trinary -->
  [1],
  operator,
  [2],
  operator,
  [3].

expr(E) :-
    phrase(expr_trinary,Expr_trinary),
    atomics_to_string(Expr_trinary,E).

1 commentaires

Évalué car il n'y a absolument aucune raison de fournir les opérateurs en tant que faits / prédicats.

4
votes

une simple récursivité:

list_combine(Ns,Os,Cs) :-
    [N|Nr] = Ns,
    member(O,Os),
    Cs = [N,O|Nt],
    list_combine(Nr,Os,Nt).

et maintenant

?- forall(list_combine([1,2,3],[+,*],C),writeln(C)).
[1,+,2,+,3]
[1,+,2,*,3]
[1,*,2,+,3]
[1,*,2,*,3]
true.

voici une - peut-être - une version plus lisible

list_combine([N|Nr],Os,[N,O|Nt]) :-
    member(O,Os),
    list_combine(Nr,Os,Nt).
list_combine([N],_,[N]).

Bien sûr, utilisez une alternative, juste pour mieux comprendre comment l'unification agit dans la décomposition et la composition des arguments.

0 commentaires

5
votes

Une variante de la belle solution postée par Carlo Capelli nous permet d'illustrer un idiome de programmation utile pour mieux exploiter l'indexation du premier argument:

list_combine([N1| Ns], Os, Nt) :-
    list_combine(Ns, N1, Os, Nt).

list_combine([], N, _, [N]).
list_combine([N2| Ns], N1, Os, [N1, O| Nt]) :-
    member(O, Os),
    list_combine(Ns, N2, Os, Nt).

L'idée est de passer la liste que nous voulons marchez en séparant la tête de la liste de la queue et passez les deux comme argument avec la queue comme premier argument, comme illustré ci-dessus.

Dans la solution originale, le compilateur Prolog ne fera généralement pas la distinction entre une liste avec un seul élément et une liste avec un ou plusieurs éléments. Mais il fera la distinction entre une liste vide (un atome) et une liste avec au moins un élément (un terme composé). Notez également que la version originale crée un faux point de choix, pour chaque appel récursif, sur l'appel au prédicat list_combine / 3 en plus du point de choix prévu sur le membre / 2 appel de prédicat.

2 commentaires

Merci, Paulo. Leçon prise :)

@CapelliC Merci d'avoir ouvert la porte :-)

1
votes

Cette proposition de ma solution, que je trouve très simple et directe, copiez et collez ci-dessous dans l'éditeur notepad ++ pour obtenir la meilleure lisibilité.

* ________________________________________________                           *
*|find_expression(NumsList,TargetValue,Expression)|                          *
**------------------------------------------------*                          *
* Expression is an arithmetic expression of the numbers in Numslist with     *
* possible operators '+','-','*','/' and '(' and ')' between the numbers     *
*  in such a way that the expression evaluates to the TargetValue argument   *  
*****************************************************************************/%

/* a single element number list can evaluate only to itself */ 
find_expression([SingleNumber],SingleNumber,SingleNumber).

/* expression of a multypile number list */ 
find_expression(NumberList,Target,Expression):-

/* non-deterministically  divide the number list 
 into 2 separate lists which include at least one number each*/ 
append([X|Xs],[Y|Ys], NumberList),

/* recursively find an expression for east list, 
   where the expression evaluates to itself */ 
find_expression([X|Xs],Exp1,Exp1),
find_expression([Y|Ys],Exp2,Exp2),

/* non-deterministically  choose an operand from [+,-,*,division] 
   and compose Expression to be (Exp1 Operand Exp2) */ 
(   member(Expression,[Exp1+Exp2,Exp1-Exp2,Exp1*Exp2]) 
    ; /* prevent zero divison */
    (Val2 is Exp2, Val2 =\= 0, Expression = (Exp1/Exp2))), %/*

/* assure that final expression evaluates(matches) the target value 
   and convert value from integer to float if necessary */
( Target = Expression ; Target is Expression 
  ; FloatTarget is Target*1.0, FloatTarget is Expression).

0 commentaires