Все возможные комбинации операций в списке номеров, чтобы найти конкретный номер

Question

Я знаю, что есть и другие вопросы, такие как мой, но единственная проблема состоит в том, что они получают все комбинации для всех вариабельных значений в списке, но я хочу, чтобы пользователь вводил желаемое число и необходимые ему числа.сделать желаемый номер.Вот код, который у меня есть:

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

и т.д ...

Все возможные решения должны быть перечислены

Все предложения будут высоко оценены

Answer 1

Вы можете использовать перестановки из модуля 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), вам нужно будет использовать комбинации больше шаблонов операторов:

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

Группировка может привести к делению на ноль, поэтому нужно попробовать: кроме блока.

Это дает следующий результат:

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)

Answer 2

Вы можете попробовать с модулем перестановок внутри itertools

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)

Answer 3

это на самом деле не очень хорошо протестировано (и, вероятно, выполняет слишком много работы), но может помочь вам начать:

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 для их оценки

Answer 4

Вот то, что я придумал, используя 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

Yeilds:

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

Урожайность

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