Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers List(2,3,5,7,11) we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).
Given 4 arithmetic operators (+, -, *, /) we will generate all combinations of equations as the potential set is finite and defined by probability.
For 5 terms, the = operator has 4 potential locations to generate equations.
Each equation creates two expressions of m, n terms | m + n = 5 and thus the number of possibilities of expressions is C(4, m - 1) for one side and C(4, n - 1) for the other side and the product of these combinations is the maximum total possibilities.
Note: that is may reduce the total number of possibilities if a '/' operator is not placed between two terms where the modulus operator would leave a remainder.
Once all the possibilities are generated the left side can be evaluated and compared with the evaluation from the right side. Possibilities with expression equality will be emitted as the solution.
Functional programming in Scala will be used to split the given list into the combinations of left and right side expressions and the built-in permutation and combination operator will suffice to generate the possibilities.
The Scala reflection Toolbox will be used to parse a string version of the possibilities evaluating both left side and right side and then comparing them to determine validity of the equation.
From invoking scala console in Intellij Idea:
import com.iscsi.EquationTree
EquationTree.main(Array(2,3,5,7,11).map(_.toString))
scala> found 14 possible paren equations found 4 possible PEMDOS equations found 21 possibilities 2=3-5-7+11 2+3=5+7/11 2+3=5-7/11 2-3+5+7=11 <<<=== given 2=(3-5)-7+11 2=(3-5-7)+11 2=(35+7)/11 <<<=== given 2=3-(5+7)+11 2=3-(5+7)/11 2=3-(5+7-11) 2=3+5/(7-11) 2=3-5-(7-11) 2+3=5+(7/11) 2+3=5-(7/11) 2-3=5/(7-11) 2(3-5)=7-11 (2-3)+5+7=11 (2-3+5)+7=11 2-(3-5)+7=11 2-(3-5-7)=11 2-3+(5+7)=11