1

I looked through here and found questions similar but not solving for the equation. Here is what I'm looking to do. I need to be able to determine a collection of equations that potentially can be used to solve a set of input parameters and a result. I will always know the inputs and the results. I need to figure out a way to solve for the solution for lack of a better term.

For instance:

Input parameters: 5,1,1,2

Result: 8

I would like to input these numbers and result and get something like:

FirstNumber(5) * (SecondNumber(1) + ThirdNumber(1)) - FourthNumber(2) = 8

FirstNumber(5) * FourthNumber(2) - SecondNumber(1) - ThirdNumber(1) = 8

Obviously it can be complex and given more numbers could have many possible solutions. My general question is around feasibility.

Kluster
  • 27
  • 1
  • Are you limited to +,-,*? Do you always have the same number of input parameters? – Alexis Olson Dec 20 '17 at 23:20
  • No, input parameters can change in quantity but for the most part the equation should be +,-,*,/. – Kluster Dec 20 '17 at 23:23
  • Do you have to use all the available numbers, or can you leave some unused? – Dawood ibn Kareem Dec 20 '17 at 23:26
  • All numbers will be used. – Kluster Dec 20 '17 at 23:28
  • Here's a **rough solution outline**. Iterate through the numbers. For each number, recurse four times, to find expressions to fit `number + ( expression ) = result`, `number * ( expression ) = result`, `number - ( expression ) = result` and `( expression ) - number = result`, where in each case `expression` is found recursively using the inputs _without_ the current number, and a different value for `result`. You'd only include the one with the `*` if `result % number == 0`. – Dawood ibn Kareem Dec 20 '17 at 23:35

2 Answers2

3

It is actually quite difficult task to solve.

First - you have to be able to solve any equation with +-*/ and with (). How to do that? You have to create tree-like structure with these operators and be able to count the result.

If you visualize the tree it looks like this: Tree

When you are finished with this task, you can start with generating all the possibilities that can happen. The Backtracking is actually quite useful, as it is automatically remove the paths that does not lead to anything and with proper implementation it finds all possible solutions.

libik
  • 22,239
  • 9
  • 44
  • 87
0

To get a collection of all possible linear equations I would try permutation without repetition for the inputs except the result (ignore possible identical inputs) and permutation taken from each cobination of all operators taken G at a time where G is the number of gaps between input numbers to fill the gaps between numbers and then try every position and size more than one and less than N for the numbers inside of the "()" where N is the number of inputs excluding the result. Check the answers in this link for how to get permutation in java Generating all permutations of a given string

USER249
  • 1,080
  • 7
  • 14