Brute-force search algorithm in arithmetic operations
<p>Since I'm a Python beginner, I'm trying to study some codes from some websites. I found in GitHub an algorithm which does a <a href="https://en.wikipedia.org/wiki/Brute-force_search" rel="nofollow">Bruteforce search</a> for arithmetic expressions. The code is:</p>

<pre><code>#!python
import operator
import itertools
from fractions import Fraction

operations = dict()
operations['+'] = operator.add
operations['-'] = operator.sub
operations['/'] = operator.truediv
operations['*'] = operator.mul

def solve(target, numbers):
    """List ways to make target from numbers."""
    numbers = [Fraction(x) for x in numbers]
    return solve_inner(target, numbers)

def solve_inner(target, numbers):
    if len(numbers) == 1:
        if numbers[0] == target:
            yield str(target)
        return

    # combine a pair of numbers with an operation, then recurse
    for a,b in itertools.permutations(numbers, 2):
        for symbol, operation in operations.items():
            try:
                product = operation(a,b)
            except ZeroDivisionError:
                continue

            subnumbers = list(numbers)
            subnumbers.remove(a)
            subnumbers.remove(b)
            subnumbers.append(product)

            for solution in solve_inner(target, subnumbers):
                # expand product (but only once)
                yield solution.replace(str(product), "({0}{1}{2})".format(a, symbol, b), 1)

if __name__ == "__main__":
    numbers = [1, 5, 6, 7]
    target = 5
    solutions = solve(target, numbers)
    for solution in solutions:
        print("{0}={1}".format(target, solution))
</code></pre>

<p>it simply ends trying any arithmetic expression using my <code>numbers</code>, then prints the ones which get the <code>target</code> as result (the result I have).</p>

<p>I'm wondering, how can I make it print any solution the script tried when the expression doesn't have as result the <code>target</code> I've set?</p>

<p>edit:</p>

<p>This is the code I tried:</p>

<pre><code>#!python
import operator
import itertools
from fractions import Fraction

operations = dict()
operations['+'] = operator.add
operations['-'] = operator.sub
operations['/'] = operator.truediv
operations['*'] = operator.mul

def solve(target, numbers):
    """List ways to make target from numbers."""
    numbers = [Fraction(x) for x in numbers]
    return solve_inner(target, numbers)

def solve_inner(target, numbers):
    if len(numbers) == 1:
        num = numbers[0]
        yield str(num), num == target
        return

    # combine a pair of numbers with an operation, then recurse
    for a,b in itertools.permutations(numbers, 2):
        for symbol, operation in operations.items():
            try:
                product = operation(a,b)
            except ZeroDivisionError:
                continue

            subnumbers = list(numbers)
            subnumbers.remove(a)
            subnumbers.remove(b)
            subnumbers.append(product)

            for solution, truth in solve_inner(target, subnumbers):
                yield solution.replace(str(product),
                    "{0}=({1}{2}{3})".format(product, a, symbol, b), 1), truth


if __name__ == "__main__":
    numbers = [1, 5, 6, 7]
    target = 5
    solutions = solve(target, numbers)
    for solution, truth in solutions:
        print("{0}? {1}".format(solution,
              'True' if truth else ''))
</code></pre>

<p>I get the actual product as result, but I get results for small operations in expressions:</p>

<pre><code>42=(7*6)/5=(42/5)=(1*42/5)
</code></pre>

<p>While I'm actually trying to get only 42 at the start of the string.</p>

<p>The recursion terminates by yielding str(num[0]) if num[0] equals target and nothing otherwise. If something is yielded, the string expression is built on successive yields.  To get all expressions, something must always be yielded.  I choose to also yield whether the target was reached.  Instead, the expression could be evaluated before printing.                  </p>

<pre><code>#!python
import operator
import itertools
from fractions import Fraction

operations = dict()
operations['+'] = operator.add
operations['-'] = operator.sub
operations['/'] = operator.truediv
operations['*'] = operator.mul

def solve(target, numbers):
    """List ways to make target from numbers."""
    numbers = [Fraction(x) for x in numbers]
    return solve_inner(target, numbers)

def solve_inner(target, numbers):
    if len(numbers) == 1:
        num = numbers[0]
        yield str(num), num == target
        return

    # combine a pair of numbers with an operation, then recurse
    for a,b in itertools.permutations(numbers, 2):
        for symbol, operation in operations.items():
            try:
                product = operation(a,b)
            except ZeroDivisionError:
                continue

            subnumbers = list(numbers)
            subnumbers.remove(a)
            subnumbers.remove(b)
            subnumbers.append(product)

            for solution, truth in solve_inner(target, subnumbers):
                # expand product (but only once)
                yield solution.replace(str(product),
                    "({0}{1}{2})".format(a, symbol, b), 1), truth

if __name__ == "__main__":
    numbers = [1, 5, 6, 7]
    target = 5
    solutions = solve(target, numbers)
    for solution, truth in solutions:
        print("{0}={1}? {2}".format(target, solution,
              'True' if truth else ''))
</code></pre>

<p>There is a glitch in the original.  The product is appended to the end, but the first number matching the product from the front is replaced.  I believe that the result could be omission of expressions, in which case the algorithm is not complete.  Since replace cannot be done starting at the end, the product should be placed at the front (<code>subnumbers.insert(0, product)</code>) so that it is the product that gets replaced.  I will let you experiment with what difference this makes.  But I believe the code would have been slightly easier to understand if written correctly.</p>

python algorithm math