问表达式与4个基本运算的组合

EN

让我们只计算一次可能的结果集(以一种更简单、更快的方式)：

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}

首先，让我们分析一下这个表达式。您有三个术语:乘积P (A*B)、商Q (A/B)和标量S。您可以将这些与加法和减法相结合。

其中两项是正的；另一项是负的，所以我们可以简单地否定三项(P，Q，S)中的一项并求和。这就减少了组合学。

乘法是可交换的；w.l.o.g，我们可以假设A>B，它将排列减半。

以下是我对第一效率的建议：

• 首先用A>B选择产品的术语；36 从剩下的7位中选择S；7*36=252选择最后6位，可能的商数范围从小于-1到max_digit / min_digit。将这些分组为等价类(一个集合用于加法，一个集合用于减法)，而不是遍历所有30个排列。这为每个案例提供了大约6个值；我们现在有大约1500个三项的组合。
  • 对于这些组合中的每一个，我们有3个可能的选择来否定其中一个；总计约为4500个和。

对于一个开始，这样的改进足够了吗？

感谢Heap Overflow指出了我错过的数据流案例(这是专业上令人尴尬的:-)。

案例A*B/C+D-E没有在上面介绍。这种方法是可比较的。

• 首先用A>B选择产品的术语；36 combinations
• Then从剩下的7位数字中选择C；combinations
• There只有38个可能的商数；你可以根据你的意愿生成这些，但由于组合这么少，蛮力也是A>B的最后6位，你有30个组合，但其中一半是另一半的否定。选择D>E开始，只需对负面的进行第二次传递。不要费心去检查重复的差异；这不值得浪费时间。
• 你现在有不到38个商可以与一定数量的差异结合(最小5，最大8，平均几乎7)。

碰巧，稍微检查一下较大的情况(除数为1的商)和剩余的各种数字，就会证明该方法将涵盖-8到77 (包括-8到77)范围内的所有整数。您不能从原始的9位数字中删除3个大数字，而不留下其差异忽略了所需间隔的数字。

如果允许您在代码中包含该分析，则可以通过反向搜索来缩短这一部分。您演示了大型案例{48，54，56，63，72}的覆盖范围，演示了较小商数的缺口填充，然后您可以在我的原始帖子中搜索复杂度较低的案例，享受您只需要78，79和小于-8的数字的知识。

我认为你只需要找到一次排列。从所有可能的和中创建一个集合。然后再做个查询。仍然有点蛮力，但省去了很多重复的计算。

def find_all_combinations():
    x = [i for i in range(1,10)]
    output_set = set()
    numbers = [str(i) for i in x]
    operators = ["+","-","*","/"]
    print("Starting Calculations", end="")
    for values in permutations(numbers,5):
        for oper in permutations(operators):
            formula = "".join(o + v for o,v in zip([""]+list(oper),values))
            # Add all the possible outputs to a set
            output_set.add(round(eval(formula)))
            print(".", end="")
    return output_set

output = find_all_combinations()

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