python - python - 如何使用回溯生成在向量的数字之间添加+和-的所有可能性，因此总和应该是正数

Question

我必须制作一个 python 应用程序来生成在向量的数字之间添加 + 和 - 的所有可能性，因此总和应该是正的，使用回溯。我写在这里是因为我不太明白如何做到这一点。

作为输入，我的应用程序得到一个整数向量：a1, a2, ... an。

我举了一个回溯应该如何工作的例子，但我不知道是否有可能实现。

（示例）对于 5 个数字：

a1 a2 a3 a4 a5

a1 + a2 + a3 + a4 + a5
a1 - a2 + a3 + a4 + a5
a1 - a2 - a3 + a4 + a5
a1 - a2 - a3 - a4 + a5
a1 - a2 - a3 - a4 - a5   
a1 + a2 - a3 + a4 + a5   
a1 + a2 - a3 - a4 + a5   
a1 + a2 - a3 - a4 - a5   
a1 + a2 + a3 - a4 + a5   
a1 + a2 + a3 - a4 - a5   
a1 + a2 + a3 + a4 - a5

这是我已经写的：

def first():
    return int(a[0])

def next(nr):
    return int(a[nr+1])

def sum(x):
    suma = 0
    for i in range(0,len(x)):
        suma += x[i] 
    if(suma <= 0):
        return False
    return True

def equal(x):
    for i in range(0,len(x)-1):
        for j in range(i+1,len(x)):
            if(x[i]==x[j]):
                return False
    return True

def isSet(x):
    if equal(x) == False:
        return False
    return True

def consistent(x,dim):
    return isSet(x)

def solution(x,dim):
    return len(x) == dim and sum(x)

def solutionFound(x,dim):
    print(x)

def backtracking(x,dim):
    # ---idea of code that doesn't work
    x=[first()] #candidate solution
    nr = -1
    while len(x)>0:
        choosed = False
        while not choosed and x[-1] < dim and nr < dim-1:
            x[-1] = next(nr) #increase the last component
            nr += 1
            choosed = consistent(x, dim)
        if choosed:
            if solution(x, dim):
                solutionFound(x, dim)
            x.append(first()) # expand candidate solution
        else:
            nr -= 1
            x = x[:-1] #go back one component
---
a = input(">>> write numbers: ").split()
n = len(a)
backtracking([],n)

如果你有任何想法，它可能是一个真正的帮助。感谢您的时间和新年快乐！

LE：非常感谢大家的回答。你帮助我了解了更多的 Python 语言。

标签： pythonbacktrackingrecursive-backtracking

Answer 1

使用函数搜索搜索 (+/-) 的二叉树。

预先计算从数组中每个索引到末尾的绝对值之和，允许在搜索中终止于中间节点。

这是因为如果到目前为止的值总和 + 从当前索引到数组末尾的值的总和 < 0，那么我们知道剩余数组中没有足够的值来克服当前的负累加值。

def findsums(a, n = -1, sumsofar = 0, signs = [], results = [], cumsum = []):

    """
    finds additions and subtraction of array element which are >= 0
        a - input array\n        
        n - highest index element of array we\'re using on the previous iteration
        sumsofar - sum using element up to index
        signs - signs (+/-) applied to these eleemnt
        results - solutions
        cumsum - cumulative sum of elements from index i to the end of array
    """
    if not cumsum:
        # Base case getting started
        #
        # Cumulative so of a in reverse order
        cumsum = cumsum_calc(a)

        # Use the first number as-is (i.e. no +/- sign)
        signs = [''] # first element is a
        sumsofar = a[0]
        n = 0

    # terminal case
    if n >= len(a)-1:
        if sumsofar >= 0:
            # terminal case (valid solution, so add)
                results.append(signs[:])
        else:
            # invalid solution
            pass # nothing to do 
    elif n == -1 or sumsofar + cumsum[n] >= 0:
        # Viable candidate so far
        # Try +/- alternatives\n        
        # Try + sign

        signs.append(' + ')
        findsums(a, n+1, sumsofar+a[n+1], signs, results, cumsum)
        signs.pop()

        # Try '-' sign
        signs.append(' - ')
        findsums(a, n+1, sumsofar-a[n+1], signs, results, cumsum)
        signs.pop()

    else:
        # Backtrack (sumsofar + cumsum[n] < 0):
        # No valid solution going forward\n        
        # So don\'t go any further with this sequence
        pass

    return results

def cumsum_calc(arr):
    " accum sum from next index forward in the array "
    # Adepted from https://www.geeksforgeeks.org/python-program-to-find-cumulative-sum-of-a-list/\n    
    # maximum sum of elements after i
    b = [abs(x) for x in arr]
    return [sum(b[i+1:]) for i in range(len(b)+1)]

def show_solutions(a, signs):
    " intertwines signs and array to show how they are added "
    # convert a to string, with parentheses around negative values

    converta = list(map(str, a))

    # place sign before each value in array a (converta)
    # function to generate list of sign, value pairs
    create_sign_value_pairs = lambda sign: list(zip(sign, converta))

    # Create sign/value pairs (i.e. [[('+', '(-1)'), ('+', '2')],...]
    sol_with_signs = list(map(create_sign_value_pairs, signs))

    # Convert each solution to a string
    solutions = list(map(lambda sol: ' '.join([''.join(s) for s in sol]), sol_with_signs))

    return "\t" + '\n\t'.join(solutions)

tests = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5]]

示例用法

测试 = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5]]

对于测试中的 t：s = findsums(t, results = []) print("对于数组 {}，解决方案是：".format(t)) print(show_solutions(t, s))

输出

For array [2, 3], solutions are:
    2  + 3
For array [-1, 2], solutions are:
    -1  + 2
For array [1], solutions are:
    1
For array [-1], solutions are:

For array [-1, -2], solutions are:
    -1  - -2
For array [1, 2, 3, 4, -5], solutions are:
    1  + 2  + 3  + 4  + -5
    1  + 2  + 3  + 4  - -5
    1  + 2  + 3  - 4  - -5
    1  + 2  - 3  + 4  - -5
    1  + 2  - 3  - 4  - -5
    1  - 2  + 3  + 4  + -5
    1  - 2  + 3  + 4  - -5
    1  - 2  + 3  - 4  - -5
    1  - 2  - 3  + 4  - -5

表现

与： arr = [-1, 1, 2, 3, 3, 1,3, 34,2,1,2,-4, -9, 2, 11]

使用 Grzegorz Skibinski（组合方法）

每个循环 760 毫秒 ± 12.7 毫秒（平均值 ± 标准偏差。7 次运行，每个循环 1 个）

当前方法（使用回溯）

每个循环 72.1 毫秒 ± 2.34 毫秒（平均值 ± 标准偏差。7 次运行，每次 10 次循环）

使用回溯比测试所有组合快 10 倍