2

new to python and 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 an error saying "TypeError: 'int' object is not utterable"

Jonathan Hall
  • 75,165
  • 16
  • 143
  • 189
Lostsoul
  • 25,013
  • 48
  • 144
  • 239
  • 1
    Are you working with Python 3? If you're working with Python 2, do `print foo` rather than `print(foo)`. – Chris Morgan Sep 02 '11 at 05:58
  • 3
    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. – steveha Sep 02 '11 at 06:00
  • 1
    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 :-) – Lostsoul Sep 02 '11 at 06:02
  • 1
    The line c in range(z/i) is not correct -- try range(int(z/i)) – Anil Shanbhag Sep 02 '11 at 06:22
  • `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)])`. – Karl Knechtel Sep 02 '11 at 06:50

2 Answers2

2

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
Chris Morgan
  • 86,207
  • 24
  • 208
  • 215
Roshan Mathews
  • 5,788
  • 2
  • 26
  • 36
  • 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. – Lostsoul Sep 03 '11 at 02:17
  • 1
    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. – Roshan Mathews Sep 03 '11 at 07:15
  • 2
    `T[a, b]` is neater than `T[(a, b)]`. – Chris Morgan Sep 03 '11 at 07:23
  • @Chris, yes, thank you. Should have noticed that. `,` makes tuples, not parentheses. – Roshan Mathews Sep 03 '11 at 09:07
  • @Chris Actually I like the explicit `tuple` better here, my brain parses it like multiple arguments to a function otherwise. Nice answer rm. – agf Sep 21 '11 at 04:15
1

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!

John Lyon
  • 11,180
  • 4
  • 36
  • 44