All possible combinations of operations on list of numbers to find a specific number

Question

I know that there are other questions like mine but the only problem is that they get all the combinations for all of the varibales in list but I want it so that the user enters the number that the want and the numbers they need to make the desired number. This is the code that I have:

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)

But I have no idea how to expand on this

This is an example on what the code should do:

Say that the number they want made is 24 and

Say the numbers that they enter are 1, 9, 8, 2

output should be this:

9 - 1 + 8 * 2 = 24

etc...

All possible solutions need to be listed

All suggestions will be greatly appriciated

Answer 1

You could use permutations from the itertools module to arrange numbers and operators in all possible ways into a string formula. Then use eval() to compute the result.

For example:

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)

[UPDATE1] If you are allowed to use the same operator more than once (as suggested by your comment on 1+1+1*8=24), you will need to use combinations_with_replacement to generate more operator patterns:

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)

Essentially, this only differs from the previous example by the insertion of the for operCombo in ... loop.

Note: The combinations will generate formulas that look exactly the same so you will want to avoid printing solutions that have already been seen (as I did here). Duplications would also occur in the previous example if any numbers were repeated in the input.

Also note that in order for 9-1+8*2 to result in 24, the multiplication must be performed before additions and subtractions (i.e. under precedence rules) otherwise 9-1+8*2=32. You would need to support parentheses to cover different orders of operation.

[UPDATE2] Supporting parentheses is a bit more involved depending on how many numbers you want to allow. For 4 numbers, there are 11 patterns:

• No parentheses: A+B+C+D
• A+B group: (A+B)+C+D
• B+C group: A+(B+C)+D
• C+D group: A+B+(C+D)
• A+B and C+D groups: (A+B)+(C+D)
• A+B+C group: (A+B+C)+D
• B+C+D group: A+(B+C+D)
• A+B group + C: ((A+B)+C)+D
• A + group B+C: (A+(B+C))+D
• B+C group + D: A+((B+C)+D)
• B + group C+D: A+(B+(C+D))

If you have more than 4 numbers there will be more patterns of parentheses grouping.

Here's an example (for 4 numbers):

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

Groupings could result in divisions by zero, so a try:except block had to be added.

This produces the following result:

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

To generate the parentheses grouping patterns for more numbers, you can use this function:

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

And then replace groups = ["X+X+X+X",... with groups = groupPatterns(len(numbers)) in the previous example.

OR, create a completely generic function for any number of values, with or without grouping and operator reuse:

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)