Calculating all possible combinations using a list of random numbers and ALL simple math operators to reach a given target
Question: I am writing a simple Python script that generates 6 numbers at random (from 1
to 100) and a larger number (from 100 to 1000). My goals for this script are
to:

  1. Calculate all of the possible combinations using at least 2 numbers and any of the simple math operations (adding, subtracting, multiplying and dividing)

  2. Output all of the combinations whose total is within 10 above or below the larger number as 'matches'

The list of numbers need not be exhausted, but repeating numbers isn't
accepted. Plus I don't care too much if the code is efficient or not (if
anyone decides to post any - I can post mine so far if anyone needs it -
preferably post it in Python); as long as it works, I'm happy to optimize it.

I have attempted this myself, only to fail as the program quickly ended with a
RunTime Error. I also tried putting in a counter to stop the loop after x
passes (where x is a small number such as 50), but that just makes matters
worse as it keeps on going infinitely.

I've also done some research, and I found that this ([Computing target number
from numbers in a set](http://stackoverflow.com/questions/2392379/computing-
target-number-from-numbers-in-a-set) \- the second to last answer) is the
closest I found to meet my requirements but hasn't got quite there yet.

Thanks for the help! :-)

EDIT: Here is my code:

    
    
    import random, time, operator
    
    i = 0
    numlist = []
    while i != 6:
        number = random.randint(1, 100)
        numlist.append(number)
        i += 1
    
    largenumber = random.randint(100, 1000)
    print(numlist)
    print(largenumber)
    
    def operationTesting():
        a, c, m, total = 0, 0, 0, 0
        totalnums = 0
        operators = ['+', '-', '*', '/']
        while total != largenumber:
            for a in numlist[m]:
                for c in numlist[m+1]:
                    print(a)
                    print(c)
                    if a == c:
                        operationTesting()
                    else:
                        b = random.choice(operators)
                        if b == '+':
                            summednums = operator.add(int(a), int(c))
                            print(summednums)
                            totalnums = totalnums + summednums
                        elif b == '-':
                            summednums = operator.sub(int(a), int(c))
                            print(summednums)
                            totalnums = totalnums + summednums
                        elif b == '*':
                            summednums = operator.mul(int(a), int(c))
                            print(summednums)
                            totalnums = totalnums + summednums
                        elif b == '/':
                            summednums = operator.floordiv(int(a), int(c))
                            print(summednums)
                            totalnums = totalnums + summednums
                        print(totalnums)
                        SystemExit(None)
    
    operationTesting()
    


Answer: A very neat way to do it is using [Reverse Polish Notation or
Postfix](http://en.wikipedia.org/wiki/Reverse_Polish_notation) notation. This
notation avoids the need for brackets that you would probably want if you were
doing it using conventional arithmetic with operator precedence etc.

You can do this with brute force if you are not too bothered about time
efficiency. You need to consider what you want to do with division too - if
two numbers do not divide exactly, do you want to return the result as
'invalid' in some way (I guess so), or really return a floored division? Note
the latter might give you some invalid answers...

Consider the test case of `numlist = [1,2,3,4,5,6]`. In RPN, we could do
something like this

    
    
    RPN           Equivalent to
    123456+++++   (1+(2+(3+(4+(5+6)))))
    123456++++-   (1-(2+(3+(4+(5+6)))))
    123456+++-+   (1+(2-(3+(4+(5+6)))))
    ...
    12345+6+-++   (1+(2+(3-((4+5)+6))))
    12345+6-+++   (1+(2+(3+((4+5)-6))))
    ...
    

And so on. You can probably see that with sufficient combinations, you can get
any combinations of numbers, operators and brackets. The brackets are
important - to take only 3 numbers obviously

    
    
    1+2*6 
    

is normally interpreted

    
    
    (1 + (2*6)) == 13
    

and is quite different to

    
    
    ((1+2)*6) == 18
    

In RPN, these would be `126*+` and `12+6*` respectively.

So, you've got to generate all your combinations in RPN, then develop an RPN
calculator to evaluate them.

Unfortunately, there are quite a lot of permutations with 6 numbers (or any
subset thereof). First you can have the numbers in any order, thats `6! = 720`
combinations. You will always need `n-1 == 5` operators and they can be any
one of the 4 operators. So that's `4**5 == 1024` permutations. Finally those 5
operators can be in any one of 5 positions (after first pair of numbers, after
first 3, after 4 and so on). You can have maximum 1 operator in the first
position, two in the second and so on. That's `5! == 120` permutations. So in
total you have `720*1024*120 == 88473600` permutations. Thats roughly `9 *
10**7` Not beyond the realms of computation at all, but it might take 5
minutes or so to generate them all on a fairly quick computer.

You could significantly improve on this by "chopping" the search tree

  1. Loads of the RPN combinations will be arithmetically identical (e.g. `123456+++++ == 12345+6++++ == 1234+5+6+++` etc) - you could use some prior knowledge to improve generate_RPN_combinations so it didn't generate them
  2. identifying intermediate results that show certain combinations could never satisfy your criterion and not exploring any further combinations down that road.

You then have to send each string to the RPN calculator. These are fairly easy
to code and a typical programming exercise - you push values onto a stack and
when you come to operators, pop the top two members from the stack, apply the
operator and push the result onto the stack. If you don't want to implement
that - google `minimal python rpn calculator` and there are resources there to
help you.

Note, you say you don't have to use all 6 numbers. Rather than implementing
that separately, I would suggest checking any intermediate results when
evaluating the combinations for all 6 numbers, if they satisfy the criterion,
keep them too.

