How to convert algorithm to python

Question

I'm having trouble converting a script to a more effective algorithm I was given.

Here's the python code:

#!/usr/bin/env python
import itertools
target_sum = 10
a = 1
b = 2
c = 4
a_range = range(0, target_sum + 1, a)
b_range = range(0, target_sum + 1, b)
c_range = range(0, target_sum + 1, c)
for i, j, k in itertools.product(a_range, b_range, c_range):
 if i + j + k == 10:
 print a, ':', i/a, ',', b, ':', j/b, ',', c, ':', k/c

(it only does 3 variables just for example, but I want to use it on thousands of variables in the end).

Here's the result I am looking for(all the combo's that make it result to 10):

1 : 0 , 2 : 1 , 4 : 2
1 : 0 , 2 : 3 , 4 : 1
1 : 0 , 2 : 5 , 4 : 0
1 : 2 , 2 : 0 , 4 : 2
1 : 2 , 2 : 2 , 4 : 1
1 : 2 , 2 : 4 , 4 : 0
1 : 4 , 2 : 1 , 4 : 1
1 : 4 , 2 : 3 , 4 : 0
1 : 6 , 2 : 0 , 4 : 1
1 : 6 , 2 : 2 , 4 : 0
1 : 8 , 2 : 1 , 4 : 0
1 : 10 , 2 : 0 , 4 : 0

In question Can brute force algorithms scale? a better algorithm was suggested but I'm having a hard time implementing the logic within python. The new test code:

 # logic to convert
 #for i = 1 to k
 #for z = 0 to sum:
 # for c = 1 to z / x_i:
 # if T[z - c * x_i][i - 1] is true: #having trouble creating the table...not sure if thats a matrix
 # set T[z][i] to true
 
#set the variables
sum = 10
data = [1, 2, 4]
# trying to find all the different ways to combine the data to equal the sum
for i in range(len(data)):
 print(i)
 if i == 0:
 continue
 for z in range(sum):
 for c in range(z/i):
 print("*" * 15)
 print('z is equal to: ', z)
 print('c is equal to: ', c)
 print('i is equal to: ', i)
 print(z - c * i)
 print('i - 1: ', (i - 1))
 
 if (z - c * i) == (i - 1):
 print("(z - c * i) * (i - 1)) match!")
 print(z,i)

Sorry its obviously pretty messy, I have no idea how to generate a table in the section that has:

if T[z - c * x_i][i - 1] is true:
 set T[z][i] to true

In other places while converting the algo, I had more problems because in lines like 'or i = 1 to k' converting it to python gives me a TypeError: 'int' object is not utterable.

• Chris Morgan: Are you working with Python 3? If you're working with Python 2, do print foo rather than print(foo).
• steveha: It's not wrong to use print(foo) in Python 2.x, so if he likes it, don't tell him not to use it! I do that a lot of the time myself when posting here.
• Lostsoul: Well Chris..I wrote this in python2 but eventually will work on changing it to python3(right now I'm a bit more familiar with python2 but I tried to be as python3-ish as possible for a newbie :-)
• Anil Shanbhag: The line c in range(z/i) is not correct -- try range(int(z/i))
• Karl Knechtel: index_accumulator.append([lol[i][indices[i]] for i in range(len(lol))]) is more idiomatically spelled index_accumulator.append(l[index] for l, index in zip(lol, indices)]).

Answer 1

You can get that block which creates the table for dynamic programming with this:

from collections import defaultdict
# T[x, i] is True if 'x' can be solved
# by a linear combination of data[:i+1]
T = defaultdict(bool) # all values are False by default
T[0, 0] = True # base case
for i, x in enumerate(data): # i is index, x is data[i]
 for s in range(sum + 1):
 for c in range(s / x + 1):
 if T[s - c * x, i]:
 T[s, i + 1] = True

• Lostsoul: Thanks for the answer, rm. I updated my question to show the output. Basically I simplified my existing script, but I am trying to get the same output as the answer in the link in my question.
• Roshan Mathews: updated - you'll still need to use this table to get back the answers you want, this will just have a True at T[(sum, len(data))] if solutions exist.
• Chris Morgan: T[a, b] is neater than T[(a, b)].
• Roshan Mathews: @Chris, yes, thank you. Should have noticed that. , makes tuples, not parentheses.
• agf: @Chris Actually I like the explicit tuple better here, my brain parses it like multiple arguments to a function otherwise. Nice answer rm.

Answer 2

You can create the table you need with a list of lists:

t = [[False for i in range(len(data))] for z in range(sum)] #Creates table filled with 'False'
for i in range(len(data)):
 print(i)
 if i == 0:
 continue
 for z in range(sum):
 for c in range(int(z/i)):
 print("*" * 15)
 print('z is equal to: ', z)
 print('c is equal to: ', c)
 print('i is equal to: ', i)
 print(z - c * i)
 print('i - 1: ', (i - 1))
 if (z - c * i) == (i - 1):
 print("(z - c * i) * (i - 1)) match!")
 t[z][i] = True # Sets element in table to 'True' 

As for your TypeError, you can't say i = 1 to k, you need to say: for i in range(1,k+1): (assuming you want k to be included).

Another tip is that you shouldn't use sum as a variable name, because this is already a built-in python function. Try putting print sum([10,4]) in your program somewhere!

• Keith: That should be for i in range(1, k+1).
• John Lyon: @Keith Cheers, one never grows out of off-by-one errors it would seem!