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

它仅会打印出未找到的整数以外的'No'。显而易见，所有整数值都可以在-71到79之间的空格中找到。

我既是使用Python还是使用算法实现的新手，但从涉及置换的事实来看，我认为该算法具有复杂度O（n！）。但是，如果不是这种情况，我仍然想要一种性能更好的算法（例如递归或动态编程）。

我无法提出一个更好的标题，因为适当的标题可能需要整个解释。而且，由于问题将涉及排列，因此组合可能会产生误导。我想...

Answer 1

首先，让我们分析一下表达式。您有三项：乘积P（A * B），商Q（A / B）和标量S。您可以将它们与加法和减法结合使用。

Answer 2

我想您只需要找到排列一次。从所有可能的总和中创建一个集合。然后进行查找。仍然有点蛮力，但是可以节省很多重复的计算。