logo标签列表

数字列表中寻找特定数字的所有可能操作组合

pythonpython-3.xnumberscombinations
4

我知道有其他类似的问题，但唯一的问题是它们会获取列表中所有变量的所有组合，但我希望用户输入所需数字和他们需要制作的目标数字。这是我拥有的代码：

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

等等...

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

任何建议将不胜感激

1
你需要使用所有四个数字吗？还是可以只使用其中的一些子集？ - Chi
@DaichiJameson 你必须使用所有的数字。 - Hass786123
“9 - 1 + 8 * 2” 和 “9 + 8 * 2 - 1” 算作不同的组合吗？ - blhsing
@blhsing 是的，它确实可以。 - Hass786123
4个回答
5
你可以使用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 上的评论建议），您需要使用 combinations_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。您需要支持括号以覆盖不同的运算顺序。

[更新2] 支持括号取决于您想要允许多少个数字。对于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 = groupPatterns(len(numbers))替换groups = ["X+X+X+X",...。

或者，为任意数量的值创建完全通用的函数，无论是否具有分组和运算符重用：

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)
这太棒了！让我自愧不如。 - Reedinationer
@Alain T. 我如何添加更多的数字来解决问题？ - Hass786123
该函数的第一个参数是一个列表，因此您可以放置任意数量的数字（如最后一个示例中所示numbersToTarget([9,8,1,2,6])）。如果您想要多个目标，则可以在循环中为每个目标调用该函数，或者将目标参数也作为列表，并在函数内部测试eval(formula) in target而不是eval(formula) == target。 - Alain T.
优秀的代码，为什么当目标数为3个时没有输出/错误？ - MacUser
2
这是我使用eval()来进行数学运算的方法（请注意，这不是非常安全的方法，恶意用户可能会通过它来攻击您的程序。如果您要部署，请查看在字符串中评估数学表达式）。
numbers = []
operators = ['+', '*', '-', '/']
desire = int(input("Enter the number you want: "))
num1 = input("Enter First number: ")
num2 = input("Enter Second number: ")
num3 = input("Enter Third number: ")
num4 = input("Enter Fourth number: ")
numbers.append(num1)
numbers.append(num2)
numbers.append(num3)
numbers.append(num4)

for operator1 in operators:
    for operator2 in operators:
        for operator3 in operators:
            problem = numbers[0] + operator1 + numbers[1] + operator2 + numbers[2] + operator3 + numbers[3]
            result = int(eval(problem))
            if result == desire:
                print("{} = {}".format(problem, result))

最初的回答

我的第一次简单测试

Enter the number you want: 40
Enter First number: 10
Enter Second number: 10
Enter Third number: 10
Enter Fourth number: 10

产量

10+10+10+10 = 40

一个更复杂的测试

Enter the number you want: 18
Enter First number: 6
Enter Second number: 3
Enter Third number: 4
Enter Fourth number: 4

输出结果：

6*3+4-4 = 18

6*3*4/4 = 18

6*3-4+4 = 18

6*3/4*4 = 18

6/3+4*4 = 18

需要注意的是，这种解决方案并没有考虑数字的各种顺序。我会看看是否能够设计出更加巧妙的方法。

更新

我已经想出了一种考虑所有数字排列的方法。

def make_order_combinations():
    number_orders = []
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for z in range(4):
                    if i != j and i != k and i != z and j != k and j != z and k != z:
                        number_orders.append((i, j, k, z))
    return number_orders


def solve_given_number_order(number_order):
    for operator1 in operators:
        for operator2 in operators:
            for operator3 in operators:
                problem = numbers[number_order[0]] + operator1 + numbers[number_order[1]] + operator2 + numbers[number_order[2]] + operator3 + numbers[number_order[3]]
                # print(problem)
                result = eval(problem)
                # print(result)
                if result == desire:
                    print("{} = {}".format(problem, result))

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

list_of_orders = make_order_combinations()
for order in list_of_orders:
    solve_given_number_order(order)

最初的回答
现在进行测试。
Enter the number you want: 67
Enter First number: 15
Enter Second number: 4
Enter Third number: 7
Enter Fourth number: 1

Yields

15*4+7*1 = 67
15*4+7/1 = 67.0
15*4+1*7 = 67
15*4*1+7 = 67
15*4/1+7 = 67.0
15*1*4+7 = 67
15/1*4+7 = 67.0
4*15+7*1 = 67
4*15+7/1 = 67.0
4*15+1*7 = 67
4*15*1+7 = 67
4*15/1+7 = 67.0
4*1*15+7 = 67
4/1*15+7 = 67.0
7+15*4*1 = 67
7+15*4/1 = 67.0
7+15*1*4 = 67
7+15/1*4 = 67.0
7+4*15*1 = 67
7+4*15/1 = 67.0
7+4*1*15 = 67
7+4/1*15 = 67.0
7+1*15*4 = 67
7*1+15*4 = 67
7/1+15*4 = 67.0
7+1*4*15 = 67
7*1+4*15 = 67
7/1+4*15 = 67.0
1*15*4+7 = 67
1*4*15+7 = 67
1*7+15*4 = 67
1*7+4*15 = 67

你可以看到它确实考虑了所有数字的重新排列。但操作顺序仍然适用，因此输出结果为：

1*7+4*15 = 67

应该理解为 (1*7)+(4*15) = 67。"Original Answer"翻译成"最初的回答"。
它确实可以工作，但由于某种原因，当我输入：1,1,1,8时，它不会输出24，即使解决方案是1 + 1 + 1 * 8 = 24，并且对于我在问题中提出的那个也不行，您知道为什么吗？ - Hass786123
无论是你的回答还是Alain T.的回答，都只是简单地翻译了内容，没有进行解释。而hiro protagonist的回答则由于某种原因没有做到这一点。 - Hass786123
你的例子（9-1+82 = 24）意味着公式必须遵循运算符优先级。当乘法在加法之前执行时（根据优先级规则），1+1+18 = 10。 - Alain T.
1
@system123456 这是由于运算顺序的原因。乘法具有更高的优先级，所以 1 + 1 + 1 * 8 -> 1 + 1 + (1 * 8) -> 1 + 1 + 8 -> 10 而不是 24。 - Reedinationer
1

这个代码并没有经过充分测试（而且可能做了太多的工作），但可以帮助你入门：

from operator import mul, add, sub, truediv
from itertools import permutations, combinations_with_replacement

operators = (mul, add, sub, truediv)
desire = 24

numbers = [1, 9, 8, 2]

OP2SYM = {mul: '*', add: '+', sub: '-', truediv: '/'}

for op0, op1, op2 in combinations_with_replacement((mul, add, sub, truediv), 3):
    for n0, n1, n2, n3 in permutations(numbers, 4):
        # print(op0, op1, op2)
        # print(n0, n1, n2, n3)
        if op0(n0, op1(n1, op2(n2, n3))) == desire:
            print('{} {} ({} {} ({} {} {}))'.format(
                n0, OP2SYM[op0], n1, OP2SYM[op1], n2, OP2SYM[op2], n3))
        if op0(op1(n0, n1), op2(n2, n3)) == desire:
            print('({} {} {}) {} ({} {} {})'.format(
                n0, OP2SYM[op0], n1, OP2SYM[op1], n2, OP2SYM[op2], n3))
        if op2(op1(op0(n0, n1), n2), n3) == desire:
            print('(({} {} {}) {} {}) {} {}'.format(
                n0, OP2SYM[op0], n1, OP2SYM[op1], n2, OP2SYM[op2], n3))

它输出

((8 * 2) + 9) - 1
((2 * 8) + 9) - 1

一个更简单的想法是构造形如'6*3-4+4'的字符串，然后使用ast.literal_eval来评估它们。
期望的数字是 24，当我输入 1,1,1,8 时，它输出了 8 * (1 + (1 + 1))，这个结果重复了6次，你知道为什么吗？ - Hass786123
排列组合中，8，1，1，1 的排列将会有六个 8，1，1，1；而对于 a，b 而言，它的排列中将会包含 b，a。如果 a = b，那么就会出现重复。可以添加一个名为 seen 的集合，如果已经在集合中见过某个组合，则直接跳过即可。 - hiro protagonist
1
你可以尝试使用 itertools 中的 permutations 模块。
from itertools import permutations, combinations
numbers = ""
solutions = []
operators = "+*-/"
desire = int(input("Enter the number you want: "))
num1 = input("Enter First number: ")
num2 = input("Enter Second number: ")
num3 = input("Enter Third number: ")
num4 = input("Enter Fourth number: ")
#concatenate the input
numbers = num1 + num2 + num3 + num4    
#generate all possible permutations of this characters
num_permutations = [p for p in permutations(numbers)]
op_combinations = [p for p in combinations(operators,3)]

for n_perm in num_permutations:
   for op_perm in op_combinations:
      cur_expression = ""
      for i in range(3):
         cur_expression += n_perm[i] + op_perm[i]
      cur_expression += n_perm[3]
      tmp_solution = eval(cur_expression)
      if desire == tmp_solution:
         solutions.append(tmp_solution)
当我运行你的代码时，出现了这个错误 tmp_solution = eval(cur_expression) TypeError: eval() arg 1 must be a string, bytes or code object。 - Hass786123
你是对的。我已经修复了：cur_expression 是一个列表而不是字符串。修复它可以让 eval() 运行并计算操作结果。 - pittix
当我输入数字时，没有任何结果显示。 - Hass786123
很明显我没有使用 print() 函数，而是让你来扩展你正在编写的代码。_solutions_ 数组将包含所有产生所需数字的字符串。 - pittix
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接