python - 找到不固定长度的数字的所有可能排列以达到给定的总和或乘积

Question

使用纯 Python 或任何 Python 库，您将如何使用 在列表 l 中找到等于给定值 val 的元素的所有可能组合加法，减法，还是乘法？假设列表的长度并不总是相同，假设列表中的每个元素在每个组合中只能使用一次，并且假设没有使用任何括号。

例如:

• 我们得到了一个数字列表:l = [1,2,3,4]
• 我们得到一个等于值组合的值:val = 6
• 输出将包括以下内容:
  • [2,4]，因为 2+4=6
  • 和[4,2]，因为4+2=6
  • 和[1,3,2]，因为1+3+2=6
  • 和[1,2,4]，因为1*2+4=6
  • 等等

---

我试过使用 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)

我只能实现测试列表中所有元素组合总和的代码。

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

我坚持使用加法、减法和乘法的组合来查找列表中元素的排列。

Answer 1

我不知道这个算法是否高效，但它运行良好:

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)

输出

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