Finding all possible permutations of an unfixed length of numbers to reach a given sum or product

Question

Using plain Python or any Python libraries, how would you go about finding all possible combinations of elements in a list l that equal a given value val using addition, subtraction, or multiplication? Assume the length of the list isn't always the same, assume each element in the list can only be used once in each combination, and assume there isn't any use of parentheses.

For example:

• We're given a list of numbers: l = [1,2,3,4]
• We're given a value equaling the combination of values: val = 6
• The output would include the following:
  • [2,4], since 2+4=6
  • And [4,2], since 4+2=6
  • And [1,3,2], since 1+3+2=6
  • And [1,2,4], since 1*2+4=6
  • etc.

---

I've tried using itertools.permutations:

>>> from itertools import permutations
>>> l = [1,2,3,4]
>>> val = 6
>>> correct_combos = []

>>> for i in range(1, len(l)+1):
...   for p in permutations(l, r=i):
...     if sum(p) == val:
...       correct_combos.append(p)

I'm able to only implement the code for testing the sum of all combinations of elements in the list.

>>> print(correct_combos)
[(2, 4), (4, 2)]

I'm stuck on finding permutations of elements in the list using a combination of addition, subtraction, and multiplication.

Answer 1

I don't know if this algorithm is efficient, but it works fine:

from itertools import permutations, product
l = [1,2,3,4]
val = 6
operator = ['+', '-', '*']
correct_combos=[]
for r in range(1, len(l)+1):
    for item in permutations(l,r):
        for unit in product(operator, repeat=r-1):
            res=""
            for idx in range(0,r-1):
                res+=str(item[idx])+unit[idx]
            res+=str(item[-1])
            if(val==eval(res)):
                if item not in correct_combos:
                    correct_combos.append(item)
print(correct_combos)

Output

[(2, 3), (2, 4), (3, 2), (4, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 4, 1), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 4, 1), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 3, 1), (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

Answer 2

You can use a recursive generator function:

from operator import add, sub, mul
l = [1,2,3,4]
val = 6
def combos(c = [], r_exp = None):
   if r_exp == val:
      yield c
   else:
      for i in filter(lambda x:x not in c, l):
         if not c:
            yield from combos(c=[i], r_exp = i)
         else:
            for s, f in [['+', add], ['-', sub], ['*', mul]]:
               yield from combos(c=c+[s, i], r_exp = f(r_exp, i))

print([''.join(map(str, i)) for i in combos()])

Output:

['1+2+3', '1-2+3+4', '1-2+4+3', '1*2*3', '1*2+4', '1+3+2', '1+3-2+4', '1+3+4-2', '1*3*2', '1+4-2+3', '1+4+3-2', '1*4+2', '1*4-2*3', '2+1+3', '2*1*3', '2*1+4', '2+3+1', '2*3', '2+4', '2*4+1-3', '2*4-3+1', '3+1+2', '3+1-2+4', '3+1+4-2', '3-1+4', '3-1*4-2', '3*1*2', '3+2+1', '3-2+1+4', '3-2+4+1', '3*2', '3+4+1-2', '3+4-1', '3+4-2+1', '4+1-2+3', '4+1+3-2', '4-1*2', '4-1+3', '4*1+2', '4*1-2*3', '4+2', '4-2+1+3', '4-2*1*3', '4-2+3+1', '4-2*3', '4*2+1-3', '4*2-3+1', '4+3+1-2', '4+3-1', '4+3-2+1']

To just get the tuple results, only a small change needs to be made:

for f in [add, sub, mull]:
   yield from combos(c=c+[i], r_exp = f(r_exp, i))
...
print(list(map(tuple, combos())))

Output:

[(1, 2, 3), (1, 2, 3, 4), (1, 2, 4, 3), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 2, 4), (1, 3, 4, 2), (1, 3, 2), (1, 4, 2, 3), (1, 4, 3, 2), (1, 4, 2), (1, 4, 2, 3), (2, 1, 3), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3), (2, 4), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2), (3, 1, 2, 4), (3, 1, 4, 2), (3, 1, 4), (3, 1, 4, 2), (3, 1, 2), (3, 2, 1), (3, 2, 1, 4), (3, 2, 4, 1), (3, 2), (3, 4, 1, 2), (3, 4, 1), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 1, 2), (4, 1, 3), (4, 1, 2), (4, 1, 2, 3), (4, 2), (4, 2, 1, 3), (4, 2, 1, 3), (4, 2, 3, 1), (4, 2, 3), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 1), (4, 3, 2, 1)]

Answer 3

Non recursive solution:

from itertools import permutations, product, accumulate
from collections import deque

from operator import add, sub, mul

l = [1, 2, 3, 4]
val = 6
correct_combos = []


def is_correct(p, val, ops=[add, sub, mul]):
    if len(p) == 1:
        return p[0] == val

    for op in product(ops, repeat=len(p) - 1):
        iop = iter(op)
        l = deque(accumulate(p, lambda a, b: next(iop)(a, b)), maxlen=1)[0]
        if l == val:
            return True

    return False


for i in range(1, len(l) + 1):
    for p in permutations(l, r=i):
        if is_correct(p, val):
            correct_combos.append(p)

print(correct_combos)

Prints:

[(2, 3), (2, 4), (3, 2), (4, 2), (1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 4, 1), (3, 1, 2), (3, 1, 4), (3, 2, 1), (3, 4, 1), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]

Answer 4

from itertools import chain, combinations


def subSet(l):
    return chain.from_iterable(combinations(l, r) for r in range(len(l) + 1))


def whatWeWant(l, val):
    x = 0
    for i in l:
        x += i
    if x == val:
        return True

    return False


l = [1, 2, 3, 4]
val = 6

allSubSets = list(subSet(l))

ans = []

for subSet in allSubSets:
    if whatWeWant(subSet, val):
        ans.append(subSet)

With this code you can find what you want but you have to specifically say the possible combinations(in whatWeWant method).