具有 4 个基本运算的表达式组合

Question

我想不出更好的标题，因为一个合适的标题可能需要完整的解释。此外，组合可能会产生误导，因为问题将涉及排列。

我想要完成的是在以下问题中超越 Python 中的蛮力方法：给定 4 个基本操作 [+,-,*,/] 和从 1 到 9 的数字，并给出 5 位数字的所有可能组合以及导致给定数字（视为整数）的 4 次不重复（排列）运算，如 1+5*9-3/7=45, 1-2/3+9*5=45,.. . 获取从可能的最低值到可能的最高值的所有整数，并找出空间中的所有整数是否存在。

我用蛮力的初步尝试如下：

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')

除了未找到的整数外，它只打印“否”。显而易见，所有整数值都可以在空间中找到，范围在 -71 到 79 之间。

我是 Python 和算法实现的新手，但我认为该算法的复杂度为 O(n!)，从涉及排列的事实来看。但如果不是这种情况，我仍然想要一种性能更好的算法（例如递归或动态编程）。

Answer 1

让我们只计算一次可能的结果集（以更简单和更快的方式）：

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

它在我的笔记本电脑上大约 4.5 秒内计算出所有可能的结果。你像这样重写大约需要 5.5 秒。这两者都比您为每个目标整数重做所有计算的方式快得多。

使用该结果集，我们可以立即回答问题，确认您的范围并显示只有 -70 和 78 缺失：

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

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