I have to make a python application that generates all possibilities of adding + and - between numbers of a vector so the sum should be positive, using backtracking. I'm writing here because I don't quite understand how to make that.
As input, my application gets a vector of integer numbers: a1, a2, ... an.
I made an example of how the backtracking should work but I don't know if it's possible to realize.
(Example) For 5 numbers:
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
This is what I already wrote:
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)
If you have any ideas, it might be a real help. Thank you for your time and Happy New Year!
L.E.: Thanks a lot to everyone for the answers you gave. You helped me to understand a bit more of the python language.
Searches through binary tree of (+/-) using a function search.
Precomputing the sum of absolute value from each index in the array to the end, allows terminating on intermediates nodes in the search.
That's because if sum of values so far + cumsum of values from the current index to the end of the array < 0, then we know there is not enough values in the remaining array to overcome the current negative accumuldated value.
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]]
Example Usage
tests = [[2, 3], [-1, 2], [1], [-1], [-1, -2], [1, 2, 3, 4, -5]]
for t in tests: s = findsums(t, results = []) print("For array {}, solutions are:".format(t)) print(show_solutions(t, s))
Output
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
Performance
With: arr = [-1, 1, 2, 3, 3, 1,3, 34,2,1,2,-4, -9, 2, 11]
Using Grzegorz Skibinski (combinations approach)
760 ms ± 12.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Current Approach (using backtracking)
72.1 ms ± 2.34 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
10X faster using backtracking as opposed to testing all the combinations