查找不固定长度的数字的所有可能排列以达到给定的总和或乘积 [英] Finding all possible permutations of an unfixed length of numbers to reach a given sum or product

问题描述

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

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.

例如:

• 我们得到了一个数字列表: 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
  • 等
  • 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.

    我尝试使用 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.

    推荐答案

    我不知道此算法是否有效，但效果很好:

    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)
    

    输出

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

    这篇关于查找不固定长度的数字的所有可能排列以达到给定的总和或乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！