Trouver toutes les permutations possibles d'une longueur non fixée de nombres pour obtenir une somme ou un produit donné.

Question

En utilisant Python ou toute autre bibliothèque Python, comment trouver toutes les combinaisons possibles d'éléments dans une liste ? l qui sont égales à une valeur donnée val en utilisant ajout , soustraction ou multiplication ? Supposons que la longueur de la liste n'est pas toujours la même, que chaque élément de la liste ne peut être utilisé qu'une fois dans chaque combinaison et que les parenthèses ne sont pas utilisées.

Par exemple :

• On nous donne une liste de chiffres : l = [1,2,3,4]
• On nous donne une valeur égale à la combinaison des valeurs : val = 6
• Le résultat serait le suivant :
  • [2,4] ya que 2+4=6
  • Et [4,2] ya que 4+2=6
  • Et [1,3,2] ya que 1+3+2=6
  • Et [1,2,4] ya que 1*2+4=6
  • etc.

---

J'ai essayé d'utiliser 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)

Je suis en mesure d'implémenter uniquement le code permettant de tester la somme de toutes les combinaisons d'éléments de la liste.

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

Je suis bloqué sur la recherche de permutations d'éléments dans la liste en utilisant une combinaison d'addition, de soustraction et de multiplication.

Answer 1

Je ne sais pas si cet algorithme est efficace, mais il fonctionne bien :

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)

Sortie

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

Vous pouvez utiliser une fonction de générateur récursif :

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

Sortie :

['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']

Pour obtenir uniquement les résultats des tuple, il suffit d'apporter une petite modification :

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

Sortie :

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

Solution non récursive :

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)

Imprimés :

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

Avec ce code, vous pouvez trouver ce que vous voulez, mais vous devez indiquer spécifiquement les combinaisons possibles (dans la méthode whatWeWant).