2

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.

Improve this question
5
  • 1
    Are you working with Python 3? If you're working with Python 2, do print foo rather than print(foo). Commented Sep 2, 2011 at 5: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. Commented Sep 2, 2011 at 6: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 :-) Commented Sep 2, 2011 at 6:02
  • 1
    The line c in range(z/i) is not correct -- try range(int(z/i)) Commented Sep 2, 2011 at 6: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)]). Commented Sep 2, 2011 at 6:50

2 Answers 2

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

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.
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.
T[a, b] is neater than T[(a, b)].
@Chris, yes, thank you. Should have noticed that. , makes tuples, not parentheses.
@Chris Actually I like the explicit tuple better here, my brain parses it like multiple arguments to a function otherwise. Nice answer rm.
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!

Improve this answer

2 Comments

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.