make_a_number.py

import itertools

def solve(n, xs):
    for t in make_trees(xs):
        if eval_tree(t) == n:
            return print_tree(t)

def make_trees(xs):
    if len(xs) == 1:
        yield ('unit', xs[0])
        return
    if not xs:
        return

    perms = itertools.permutations(xs)
    for p in perms:
        for partition in range(len(p)):
            for op in ['+', '-', '*', '/']:
                lhs_trees = make_trees(p[:partition])
                rhs_trees = make_trees(p[partition:])
                for lhs in lhs_trees:
                    for rhs in rhs_trees:
                        yield (op, lhs, rhs)

def eval_tree(t):
    if t[0] == 'unit':
        return t[1]

    op, lhs, rhs = t
    lhs_v = eval_tree(lhs)
    if lhs_v is None:
        return None

    rhs_v = eval_tree(rhs)
    if rhs_v is None:
        return None

    if op == '+':
        return lhs_v + rhs_v
    if op == '-':
        return lhs_v - rhs_v
    if op == '*':
        return lhs_v * rhs_v
    if op == '/' and rhs_v != 0 and lhs_v % rhs_v == 0:
        return lhs_v / rhs_v

    # Invalid tree (divide by zero or fraction)
    return None

def print_tree(t):
    if t is None:
        return ''

    if t[0] == 'unit':
        return str(t[1])

    op, lhs, rhs = t
    lhs_v = print_tree(lhs)
    rhs_v = print_tree(rhs)
    if op == '+':
        return '({}) + ({})'.format(lhs_v, rhs_v)
    if op == '-':
        return '({}) - ({})'.format(lhs_v, rhs_v)
    if op == '*':
        return '{} * {}'.format(lhs_v, rhs_v)
    if op == '/':
        return '{} / {}'.format(lhs_v, rhs_v)