python - 使用随机数列表和所有简单的数学运算符计算所有可能的组合以达到给定目标

Question

我正在编写一个简单的 Python 脚本，它随机生成 6 个数字(从 1 到 100)和一个更大的数字(从 100 到 1000)。我对这个脚本的目标是:

1. 使用至少 2 个数字和任何简单的数学运算(加、减、乘和除)计算所有可能的组合

2. 将总和在大于或小于较大数的 10 以内的所有组合输出为“匹配”

数字列表无需穷尽，但不接受重复数字。另外，我不太关心代码是否有效(如果有人决定发布任何代码——如果有人需要，我可以发布我的代码——最好用 Python 发布)；只要它有效，我很乐意对其进行优化。

我自己也尝试过，但由于程序很快以运行时错误结束而失败。我还尝试在 x 通过后放入一个计数器来停止循环(其中 x 是一个很小的数字，例如 50)，但这只会让事情变得更糟，因为它会无限地继续下去。

我也做了一些研究，我发现这个(Computing target number from numbers in a set - 倒数第二个答案)是我发现最接近我的要求但还没有完全达到要求。

感谢您的帮助! :-)

编辑:这是我的代码:

import random, time, operator

i = 0
numlist = []
while i != 6:
    number = random.randint(1, 100)
    numlist.append(number)
    i += 1

largenumber = random.randint(100, 1000)
print(numlist)
print(largenumber)

def operationTesting():
    a, c, m, total = 0, 0, 0, 0
    totalnums = 0
    operators = ['+', '-', '*', '/']
    while total != largenumber:
        for a in numlist[m]:
            for c in numlist[m+1]:
                print(a)
                print(c)
                if a == c:
                    operationTesting()
                else:
                    b = random.choice(operators)
                    if b == '+':
                        summednums = operator.add(int(a), int(c))
                        print(summednums)
                        totalnums = totalnums + summednums
                    elif b == '-':
                        summednums = operator.sub(int(a), int(c))
                        print(summednums)
                        totalnums = totalnums + summednums
                    elif b == '*':
                        summednums = operator.mul(int(a), int(c))
                        print(summednums)
                        totalnums = totalnums + summednums
                    elif b == '/':
                        summednums = operator.floordiv(int(a), int(c))
                        print(summednums)
                        totalnums = totalnums + summednums
                    print(totalnums)
                    SystemExit(None)

operationTesting()

Answer 1

一种非常简洁的方法是使用 Reverse Polish Notation or Postfix 表示法。如果您使用具有运算符优先级的传统算术等，这种表示法避免了您可能需要的括号。

如果您不太在意时间效率，您可以使用蛮力来完成此操作。你还需要考虑你想用除法做什么——如果两个数字不能完全除法，你是想以某种方式将结果返回为“无效”(我猜是这样)，还是真的返回一个底数除法？请注意，后者可能会给您一些无效的答案...

考虑 numlist = [1,2,3,4,5,6] 的测试用例。在 RPN 中，我们可以做这样的事情

RPN           Equivalent to
123456+++++   (1+(2+(3+(4+(5+6)))))
123456++++-   (1-(2+(3+(4+(5+6)))))
123456+++-+   (1+(2-(3+(4+(5+6)))))
...
12345+6+-++   (1+(2+(3-((4+5)+6))))
12345+6-+++   (1+(2+(3+((4+5)-6))))
...

等等。您可能会看到，通过足够的组合，您可以获得数字、运算符和括号的任意组合。括号很重要——显然只取 3 个数字

1+2*6 

通常被解释为

(1 + (2*6)) == 13

和

完全不同

((1+2)*6) == 18

在 RPN 中，它们分别是 126*+ 和 12+6*。

因此，您必须在 RPN 中生成所有组合，然后开发一个 RPN 计算器来评估它们。

不幸的是，有很多 6 个数字(或其任何子集)的排列。首先，您可以按任意顺序排列数字，即 6! = 720 组合。您将始终需要 n-1 == 5 运算符，它们可以是 4 个运算符中的任何一个。这就是 4**5 == 1024 排列。最后，这 5 个运算符可以位于 5 个位置中的任何一个(在第一对数字之后、在前 3 个之后、在 4 之后，依此类推)。您最多可以在第一个位置有 1 个运算符(operator)，在第二个位置有两个，依此类推。那是 5! == 120 排列。所以总共有 720*1024*120 == 88473600 排列。这大约是 9 * 10**7 根本没有超出计算范围，但在相当快的计算机上生成它们可能需要 5 分钟左右。

您可以通过“砍掉”搜索树来显着改进这一点

1. RPN 组合的负载在算术上是相同的(例如 123456+++++ == 12345+6++++ == 1234+5+6+++ 等)- 你可以使用一些先验知识来改进 generate_RPN_combinations，因此它不会生成它们
2. 确定显示某些组合的中间结果永远不会满足您的标准，并且不会沿着这条路探索任何进一步的组合。

然后您必须将每个字符串发送到 RPN 计算器。这些都是相当容易编写代码和典型的编程练习——将值压入堆栈，当你遇到运算符时，从堆栈中弹出顶部的两个成员，应用运算符并将结果压入堆栈。如果您不想实现它 - 谷歌 minimal python rpn calculator 那里有可以帮助您的资源。

请注意，您说您不必使用全部 6 个数字。与其单独实现，我建议在评估所有 6 个数字的组合时检查任何中间结果，如果它们满足标准，也保留它们。