Deduction of Integer Math (Order of Operations)
Question: I'm working in Python at the moment, and I'm coming to a problem I don't know
where to grab straws. Forgive me if this is covered in some initial Algorithm
CS class somewhere, my background is really in Economics. I'm working with
financial data, and I know the output and the inputs, I just don't know how to
get to the order of operations.

For instance, I have a final price to earnings ratio of 2, but inputs of 10
(price) and 5 (earnings). Just looking at this, I know 10/5 would be
equivalent to 2. However, the problem is the order of operations .... this
could be either addition, multiplication, division and square roots.

This part seems doable if I just had

    
    
    inputs = [10,5]
    output = 2
    
    def deduction_int(inputs, output):
        initial_output = 0
        while initial_output != output:
        try adding, try subtracting (inverse), try dividing(inverse)
    

prints 'yay' when its got itself figured out or if there is an answer

The above code seems obvious and quick, however, when you add 3 variables to
it ....

inputs : 10, 5, 7 output : 2.14

and situations such as (10 + 5) / 7 = 2.14.

I'm stuck with situations where numbers might be run with a different order.
For instance 10+5 runs before dividing by 7. Is this a common algorithm type
of problem? If so, where exactly do I look for some textbook description (name
of the algorithm, textbook)?

Thanks!


Answer: Here is a brute-force algorithm.

    
    
    from __future__ import division
    import itertools as IT
    import operator
    
    opmap = {operator.add: '+',
             operator.mul: '*',
             operator.truediv: '/'}
    operators = opmap.keys()
    
    def deduction_int(inputs, output):
        iternums = IT.permutations(inputs, len(inputs))
        iterops = IT.product(operators, repeat=len(inputs)-1)
        for nums, ops in IT.product(iternums, iterops):
            for result, rstr in combine(nums, ops):
                if near(result, output, atol=1e-3):
                    return rstr
    
    def combine(nums, ops, astr=''):
        a = nums[0]
        astr = astr if astr else str(a)
        try:
            op = ops[0]
        except IndexError:
            return [(a, astr)]
        # combine a op (...)
        result = []
        for partial_val, partial_str in combine(nums[1:], ops[1:]):
            r = op(a, partial_val)
            if len(nums[1:]) > 1:
                rstr = '{}{}({})'.format(astr, opmap[op], partial_str)
            else:
                rstr = '{}{}{}'.format(astr, opmap[op], partial_str)
            assert near(eval(rstr), r)
            result.append((r, rstr))
        # combine (a op ...)
        b = nums[1]
        astr = '({}{}{})'.format(astr,opmap[op], b)
        for partial_val, partial_str in combine((op(a, b),)+nums[2:], ops[1:],
                                                astr):
            assert near(eval(partial_str), partial_val)
            result.append((partial_val, partial_str))
        return result
    
    def near(a, b, rtol=1e-5, atol=1e-8):
        return abs(a - b) < (atol + rtol * abs(b))
    
    def report(inputs, output):
        rstr = deduction_int(inputs, output)
        return '{} = {}'.format(rstr, output)
    
    print(report([10,5,7], (10+5)/7))
    print(report([1,2,3,4], 3/7.))
    print(report([1,2,3,4,5], (1+(2/3)*(4-5))))
    

yields

    
    
    (10+5)/7 = 2.14285714286
    (1+2)/(3+4) = 0.428571428571
    (1+5)/((2+4)*3) = 0.333333333333
    

* * *

The main idea is to simply enumerate all orderings of the input values, and
all orderings of the operators. For example,

    
    
    In [19]: list(IT.permutations([10,5,7], 3))
    Out[19]: [(10, 5, 7), (10, 7, 5), (5, 10, 7), (5, 7, 10), (7, 10, 5), (7, 5, 10)]
    

Then you pair each ordering of the input values with each ordering of the
operators:

    
    
    In [38]: list(IT.product(iternums, iterops))
    Out[38]: 
    [((10, 5, 7), (<built-in function add>, <built-in function mul>)),
     ((10, 5, 7), (<built-in function add>, <built-in function truediv>)),
     ((10, 5, 7), (<built-in function mul>, <built-in function add>)),
     ((10, 5, 7), (<built-in function mul>, <built-in function truediv>)),
     ...
    

The `combine` function takes an ordering of the nums and an ordering of the
ops, and enumerates all possible groupings of the nums and ops: In [65]:
combine((10, 5, 7), (operator.add, operator.mul))

    
    
    Out[65]: [(45, '10+(5*7)'), (45, '10+((5*7))'), (105, '(10+5)*7'), (105, '((10+5)*7)')]
    

It returns a list of tuples. Each tuple is a 2-tuple consisting of a numerical
value and the string representation, `rstr`, of the grouped operations which
evaluates to that value.

So, you just loop over every possibility and return the `rstr` which, when
evaluated, produces a number close to `output`.

    
    
    for nums, ops in IT.product(iternums, iterops):
        for result, rstr in combine(nums, ops):
            if near(result, output, atol=1e-3):
                return rstr
    

* * *

**Some useful references:**

  * [itertools.permutations](http://docs.python.org/2/library/itertools.html#itertools.permutations)
  * [itertools.product](http://docs.python.org/2/library/itertools.html#itertools.product)
  * [itertools.izip](http://docs.python.org/2/library/itertools.html#itertools.izip)

