时间戳

首页 > 解决方案 > 对数字列表进行所有可能的操作组合以查找特定数字

python - 对数字列表进行所有可能的操作组合以查找特定数字

问题描述

我知道还有像我这样的其他问题，但唯一的问题是他们获得了列表中所有变量的所有组合，但我想要它以便用户输入想要的数字和他们需要的数字数字。这是我拥有的代码：

numbers = []
operators = ['+', '*', '-', '/']
desire = int(input("Enter the number you want: "))
num1 = int(input("Enter First number: "))
num2 = int(input("Enter Second number: "))
num3 = int(input("Enter Third number: "))
num4 = int(input("Enter Fourth number: "))
numbers.append(num1)
numbers.append(num2)
numbers.append(num3)
numbers.append(num4)

但我不知道如何扩展这个

这是代码应该做什么的示例：

说他们想要的数字24是

说他们输入的数字是1, 9, 8, 2

输出应该是这样的：

9 - 1 + 8 * 2 = 24

ETC...

需要列出所有可能的解决方案

所有的建议都将不胜感激

标签： pythonpython-3.xnumberscombinations

解决方案

您可以使用 itertools 模块中的排列以所有可能的方式将数字和运算符排列到字符串公式中。然后使用 eval() 计算结果。

例如：

from itertools import permutations
numbers   = ["1","9","8","2"]
target    = 24
operators = ["+","-","*","/"]
for values in permutations(numbers,len(numbers)):
    for oper in permutations(operators,len(numbers)-1):
        formula = "".join(o+v for o,v in zip([""]+list(oper),values))
        if eval(formula) == target: print(formula,"=",target)

[更新1]如果您被允许多次使用同一个运算符（如您对 1+1+1*8=24 的评论所建议的那样），您将需要使用 combination_with_replacement 生成更多运算符模式：

from itertools import permutations,combinations_with_replacement
numbers   = ["1","1","1","8"]
target    = 10
operators = ["+","-","*","/"]
seen      = set()
for values in permutations(numbers,len(numbers)):
    for operCombo in combinations_with_replacement(operators,len(numbers)-1):
        for oper in permutations(operCombo,len(numbers)-1):
            formula = "".join(o+v for o,v in zip([""]+list(oper),values))
            if formula not in seen and eval(formula) == target:
                print(formula,"=",target)
                seen.add(formula)

本质上，这与前面的例子的不同之处在于for operCombo in ...循环的插入。

注意：组合将生成看起来完全相同的公式，因此您将希望避免打印已经见过的解决方案（就像我在这里所做的那样）。如果输入中重复了任何数字，则在前面的示例中也会出现重复。

还要注意，为了使 9-1+8*2 得到 24，乘法必须在加法和减法之前执行（即在优先规则下），否则 9-1+8*2=32。您需要支持括号以涵盖不同的操作顺序。

[UPDATE2]支持括号会涉及更多，具体取决于您要允许多少个数字。对于 4 个数字，有 11 种模式：

  • 无括号：A+B+C+D
  • A+B组：(A+B)+C+D
  • B+C组：A+(B+C)+D
  • C+D组：A+B+(C+D)
  • A+B 和 C+D 组：(A+B)+(C+D)
  • A+B+C组：（A+B+C）+D
  • B+C+D组：A+(B+C+D)
  • A+B组+C：((A+B)+C)+D
  • A + B+C组：(A+(B+C))+D
  • B+C组+D：A+((B+C)+D)
  • B+C+D组：A+(B+(C+D))

如果您有超过 4 个数字，则会有更多的括号分组模式。

这是一个例子（4个数字）：

from itertools import permutations,combinations_with_replacement
numbers   = ["9","8","1","2"]
target    = 24
operators = ["+","-","*","/"]
groups    = ['X+X+X+X', 'X+X+(X+X)', 'X+(X+X)+X', '(X+X+X)+X', '(X+X)+X+X', 'X+(X+X+X)', '((X+X)+X)+X', 'X+(X+(X+X))', 'X+((X+X)+X)', '(X+X)+(X+X)', '(X+(X+X))+X']
seen      = set()
for values in permutations(numbers,len(numbers)):
    for operCombo in combinations_with_replacement(operators,len(numbers)-1):
        for oper in permutations(operCombo,len(numbers)-1):
            formulaKey = "".join(oper+values)
            if formulaKey in seen: continue # ignore variations on parentheses alone
            for pattern in groups:
                formula = "".join(o+p for o,p in zip([""]+list(oper), pattern.split("+")))
                formula = "".join(v+p for v,p in zip([""]+list(values),formula.split("X")))
                try:
                    if eval(formula) == target:
                        print(formula,"=",target)
                        seen.add(formulaKey)
                        break 
                except: pass

分组可能导致除以零，因此必须添加 try:except 块。

这会产生以下结果：

9*8/(1+2) = 24
9+8*2-1 = 24
9*8/(2+1) = 24
9-1+8*2 = 24
9-(1-8*2) = 24
9-1+2*8 = 24
(9-1)*2+8 = 24
9/(1+2)*8 = 24
9/((1+2)/8) = 24
9-(1-2*8) = 24
9+2*8-1 = 24
9/(2+1)*8 = 24
9/((2+1)/8) = 24
8+(9-1)*2 = 24
8*9/(1+2) = 24
8*9/(2+1) = 24
8-(1-9)*2 = 24
8/(1+2)*9 = 24
8/((1+2)/9) = 24
8+2*(9-1) = 24
8*2+9-1 = 24
8*2-1+9 = 24
8/(2+1)*9 = 24
8/((2+1)/9) = 24
8-2*(1-9) = 24
8*2-(1-9) = 24
2*(9-1)+8 = 24
2*8+9-1 = 24
2*8-1+9 = 24
2*8-(1-9) = 24

要为更多数字生成括号分组模式，您可以使用此函数：

from itertools import product
import re
def groupPatterns(count,pattern=None):
    arr = pattern or "X"*count
    if len(arr) < 2 : return [arr]
    result = []
    for mid in range(1,len(arr)):
        leftPattern  = groupPatterns(count,arr[:mid])
        rightPattern = groupPatterns(count,arr[mid:])
        for left,right in product(leftPattern,rightPattern):
            result += [left + right]
            if len(left)  > 1 : result += ["(" + left + ")" + right]
            if len(right) > 1 : result += [left + "(" + right + ")"]
            if len(left) > 1 and len(right) > 1: 
                result += ["(" + left + ")(" + right + ")"]
    if pattern: return result # recursion
    patterns = [] # final, add "+" between X value placeholders or groups
    for pat in sorted(set(result),key=lambda x:len(x)):
        pat = re.sub("X(?=X)", r"X+",  pat)  # XX --> X+X
        pat = re.sub("X\(",    r"X+(", pat)  # X( --> X+(
        pat = re.sub("\)X",    r")+X", pat)  # )X --> )+X
        pat = re.sub("\)\(",   r")+(", pat)  # )( --> )+(
        patterns.append(pat)
    return patterns

然后在前面的示例中groups = ["X+X+X+X",...替换为。groups = groupPatterns(len(numbers))

或者，为任意数量的值创建一个完全通用的函数，有或没有分组和运算符重用：

from itertools import permutations,combinations_with_replacement
def numbersToTarget(numbers,target,reuseOper=True,allowGroups=True,operators=["+","-","*","/"]):   
    groups      = groupPatterns(len(numbers)) if allowGroups else [ "+".join("X"*len(numbers)) ]
    seen        = set()
    for values in permutations(numbers,len(numbers)):
        for operCombo in combinations_with_replacement(operators,len(numbers)-1) if reuseOper else [operators]:
            for opers in permutations(operCombo,len(numbers)-1):
                formulaKey = str(opers)+str(values)
                if formulaKey in seen: continue # ignore variations on parentheses alone
                for pattern in groups:
                    formula = "".join(o+p      for o,p in zip([""]+list(opers), pattern.split("+")))
                    formula = "".join(str(v)+p for v,p in zip([""]+list(values),formula.split("X")))
                    try:
                        if eval(formula) == target:
                            seen.add(formulaKey)
                            yield formula
                            break 
                    except: pass

for formula in numbersToTarget([9,8,1,2],24):
    print("24 =",formula)
for formula in numbersToTarget([9,8,1,2,5],0,allowGroups=False):
    print("0 =",formula)

推荐阅读