dkhara
dkhara

Reputation: 715

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

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:


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.

Upvotes: 2

Views: 171

Answers (4)

Cute Panda
Cute Panda

Reputation: 1498

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)]

Upvotes: 4

Ajax1234
Ajax1234

Reputation: 71471

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)]

Upvotes: 3

Andrej Kesely
Andrej Kesely

Reputation: 195653

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)]

Upvotes: 3

Ahmadreza Salimi
Ahmadreza Salimi

Reputation: 11

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).

Upvotes: 0

Related Questions