Given something like this:
1 5 3 4 = 18
I need to determine (using an algorithm) if there is a combination of operators and brackets that bring me to 18. Only "+" and "*" and "(" and ")" are allowed.
Example:
1 + 5 + ( 3 * 4 ) = 18
Beside brute force, is there any particular algorithm that is able to compute all the possible combo in reasonable time? RPN may help in order to encode the possible solutions, but the same are a lot (4^n ?).
Brute force is actually quite fast if you avoid pointless calculations.
In the worst case you have 2^(N-1) operators and N!(N-1)! ways of choosing the pairs of numbers for the N-1 operations. So for example, for N=4, this gives 1,152 possibilities.
But you can cut this down substabtially: if you are going to look at 6+2 and 6*2, then there is no need to look at 2+6 and 2*6: just do the bigger number first. This takes out a factor of 2^(N-1) bringing the number of possibilities down to N!(N-1)!, so 144 for N=4.
There are further possible savings as (20+6)+2 is the same as 20+(6+2), but I suspect this may not be worth optimising for until N becomes large. Another is that multiplication by 1 does not help much: this kind of thing may not be a saving with N=4, but could be if you were also for example looking at division (especially if the smaller number is not a factor or divisor of the larger number) as you can then remove a bunch of possibilities. rzzzwilson's suggestion of stopping when the target is exceeded works in a similar way, though only works if the all the operations are non-decreasing (i.e addition and multiplication but not subtraction or division)
As an illustration of something similar, try my old Java applet here, with six numbers and four operators. You can put your own numbers and target in the box. It is not prettily programmed, but is still quite quick.
Interesting problem.
I haven't written any code, but here's my thoughts. I haven't been able to think of an approach beyond brute force, with a little 'pruning'.
Using an RPN representation is the way to go, as it simplifies the handling of brackets (as such, they go away). Using your example, the RPN is 1 5 . 3 . 4 . where every '.' is a place where an operator might be, except for the right-most '.' where we know there has to be one or more operators, because it's RPN. Every other '.' has zero or more operators. For N values you must have N-1 operators, of course.
Now the problem splits into these parts: 1. Generate all combinations of N-1 operators (2^N) 2. For each operator combination, generate all 'fillings' of the operator points '.', ie, group the operator list by 1s, 2s, ..., N-1s, maintaining the operator order (my combinatorics-fu is weak, can't figure this out) 3. For each combination of combinations, evaluate the expression
The pruning occurs in the last step. As you evaluate, if the expression value goes beyond the desired result, stop with a fail, as there are no operators that might reduce the expression value.
This problem is NP complete and therefore cannot be expected to be solveable in anything less than O(n!). However, as in all NP complete problems, you can of course approximate an algorithm that would get you close to 18, or alternatively, generate a list of similar numbers with operators that would result in 18.
