python-如何使用回溯生成在向量的数字之间添加+和-的所有可能性,以便总和为正

Bianca G • 6 年前 • 2296 次点击

我必须制作一个python应用程序,它生成在向量的数字之间添加+和-的所有可能性,因此总和应该是正的,使用回溯。我写这篇文章是因为我不太懂怎么做。

作为输入,我的应用程序得到一个整数向量:a1,a2。。。安。

我举例说明了回溯应该如何工作,但我不知道是否有可能实现。

(示例)对于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)

五十、 E:非常感谢大家的回答。你帮助我了解了更多的python语言。

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/53184

文章 [ 4 ] | 最新文章 6 年前

• 1 楼

Yacine Mahdid 6 年前

从您的评论中可以看出,有效序列的要求是它在求和的末尾是正的。中间结果可能是否定的,这无关紧要。

回溯因为一旦你在一片叶子上,你输出了一个结果,你需要返回并回溯以测试另一种可能性。这种回溯可以很容易地实现使用递归与击中一个离开是基本情况。若要仅在结尾处输出完整的求和,您可以将对应于节点标签的字符串列表和迄今为止所采用的路径作为参数。

希望有帮助!

• 2 楼

Grzegorz Skibinski 6 年前

使用 itertools

import itertools

v=[3,5,-7,2,-3,1,-1]

def next_combination(v):
    v=[str(el) for el in v]
    for op in itertools.product(["-","+"], repeat=len(v)-1):
        x=list(itertools.chain.from_iterable(zip(v,op))) + [v[-1]]
        if(eval(''.join(x))>0):
            yield x

for el in next_combination(v):
    print(el)

输出:

['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '-', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '-', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '-', '1', '+', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']
['3', '+', '5', '-', '-7', '+', '2', '+', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '-', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '-', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '-', '-1']
['3', '+', '5', '+', '-7', '+', '2', '-', '-3', '+', '1', '+', '-1']
['3', '+', '5', '+', '-7', '+', '2', '+', '-3', '+', '1', '-', '-1']

• 3 楼

Ajax1234 6 年前

ops = {'+':lambda x, y:x+y, '-':lambda x, y:x-y}
def _eval(d):
   return d[0] if len(d) == 1 else _eval([ops[d[1]](d[0], d[2]), *d[3:]])

def combos(vals, l, c = []):
  if not vals:
     yield c
  else:
     for i in ['+', '-']:
        if len(c) < l-1 or _eval([*c, i, vals[0]]) > 0:
           yield from combos(vals[1:], l, c+[i, vals[0]])


print(list(combos([1, 2, 3, 4, 5], 5, [1])))

输出:

[[1, '+', 1, '+', 2, '+', 3, '+', 4, '+', 5], 
 [1, '+', 1, '+', 2, '+', 3, '+', 4, '-', 5], 
 [1, '+', 1, '+', 2, '+', 3, '-', 4, '+', 5], 
 [1, '+', 1, '+', 2, '-', 3, '+', 4, '+', 5], 
 [1, '+', 1, '-', 2, '+', 3, '+', 4, '+', 5], 
 [1, '+', 1, '-', 2, '+', 3, '+', 4, '-', 5], 
 [1, '-', 1, '+', 2, '+', 3, '+', 4, '+', 5], 
 [1, '-', 1, '+', 2, '+', 3, '+', 4, '-', 5], 
 [1, '-', 1, '+', 2, '+', 3, '-', 4, '+', 5], 
 [1, '-', 1, '-', 2, '+', 3, '+', 4, '+', 5]]

• 4 楼

DarrylG 6 年前

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

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

这是因为,如果到目前为止的值之和+从当前索引到数组末尾的值之和<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: print(“对于数组{},解决方案是:”.format(t)) 打印(显示解决方案(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

性能

使用Grzegorz Skibinski(组合法)

当前方法(使用回溯)

72.1 ms±2.34 ms/回路(7次运行的平均值±标准偏差,每个10回路)

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

登录后回复