Combinations of expressions with 4 elementary operations

Question

I could not come up with a better title, for an adequate one might require the whole explanation. Also, combinations could be misleading since the problem will involve permutations.

What I want to accomplish is to outperform a brute force approach in Python at the following problem: Given the 4 elementary operations [+,-,*,/] and the digits from 1 to 9, and given all the possible combinations of 5 digits and the 4 operations without repetition (permutations) that result in a given number (treated as an integer), as in 1+5*9-3/7=45, 1-2/3+9*5=45,... obtain all the integers from the lowest possible value to the highest possible value and find out wether all the integers in the space expanse exist.

My preliminary attempt with brute force is the following:

def brute_force(target):
    temp = 0
    x = [i for i in range(1,10)]
    numbers = [str(i) for i in x]
    operators = ["+","-","*","/"]
    for values in permutations(numbers,5):
        for oper in permutations(operators):
            formula = "".join(o + v for o,v in zip([""]+list(oper),values))
            if round(eval(formula)) == int(target):
                temp += 1
    if temp > 0:
        return True
    else:
        return False

for i in range(-100,100):
    total = brute_force(i)
    if total:
        print(i)
    else:
        print(str(i) + 'No')

It just prints 'No' besides the integers that have not been found. As may seem obvious, all integer values can be found in the space expanse, ranging between -71 to 79.

I am sort of a newcommer both with Python and with algorithmic implementation, but I think that the algorithm has complexity O(n!), judging by the fact that permutations are involved. But if that is not the case I nevertheless want an algorithm that performs better (such as recursion or dynamic programming).

Answer 1

First of all, let's look at the expression analytically. You have three terms: a product P (A*B), a quotient Q (A/B), and a scalar S. You combine these with an addition and a subtraction.

Two of the terms are positive; the other is negative, so we can simply negate one of the three terms (P, Q, S) and take the sum. This cuts down the combinatorics.

Multiplication is commutative; w.l.o.g, we can assume A>B, which cuts the permutations in half.

Here are my suggestion for first efficiency:

• First choose the terms of the product with A>B; 36 combinations
• Then choose S from the remaining 7 digits; 7*36=252 combinations
• From the last 6 digits, the possible quotients range from less-than-1 through max_digit / min_digit. Group these into equivalence classes (one set for addition, one for subtraction), rather than running through all 30 permutations. This gives us roughly 6 values per case; we now have ~1500 combinations of three terms.
• For each of these combinations, we have 3 possible choices for which one to negate; total is ~4500 sums.

Is that enough improvement for a start?

---

Thanks to Heap Overflow for pointing out the data flow case I missed (this is professionally embarrassing :-) ).

The case A*B/C+D-E is not covered above. The approach is comparable.

• First choose the terms of the product with A>B; 36 combinations
• Then choose C from the remaining 7 digits; 7*36=252 combinations
• There are only 38 total possible quotients; you can generate these as you wish, but with so few combinations, brute-force is also reasonable.
• From the last 6 digits, you have 30 combinations, but half of them are negations of the other half. Choose D>E to start and merely make a second pass for the negative ones. Don't bother to check for duplicated differences; it's not worth the time.
• You now have less than 38 quotients to combine with a quantity of differences (min 5, max 8, mean almost 7).

As it happens, a bit of examination of the larger cases (quotients with divisor of 1) and the remaining variety of digits will demonstrate that this method will cover all of the integers in the range -8 through 77, inclusive. You cannot remove 3 large numbers from the original 9 digits without leaving numbers whose difference omits needed intervals.

If you're allowed to include that analysis in your coding, you can shorten this part by reversing the search. You demonstrate the coverage for the large cases {48, 54, 56, 63, 72}, demonstrate the gap-filling for smaller quotients, and then you can search with less complication for the cases in my original posting, enjoying the knowledge that you need only 78, 79, and numbers less than -8.

Answer 2

Let's compute the set of possible results only once (and in a bit simpler and faster way):

expression = [None] * 9
results = {eval(''.join(expression))
           for expression[::2] in permutations('123456789', 5)
           for expression[1::2] in permutations('+-*/')}

It computes all possible results in about 4.5 seconds on my laptop. Yours rewritten like this takes about 5.5 seconds. Both of which are much faster than your way of redoing all calculations for every target integer.

Using that results set, we can then answer questions instantaneously, confirming your range and showing that only -70 and 78 are missing:

>>> min(results), max(results)
(-70.71428571428571, 78.83333333333333)

>>> set(range(-70, 79)) - results
{-70, 78}