如何将算法转换为Python

Question

我刚开始学Python，正在尝试把一个脚本转换成更有效的算法，但遇到了一些困难。

这是我现在的Python代码：

#!/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

（这个代码只处理了3个变量，主要是为了举个例子，但我最终想用它处理成千上万个变量）。

我想要的结果是（所有组合加起来等于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

在这个问题中 暴力算法能扩展吗？ 有人建议了一个更好的算法，但我在Python中实现这个逻辑时遇到了麻烦。新的测试代码是：

    # 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)

抱歉，代码看起来有点乱，我不知道怎么在下面这部分生成一个表：

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

在转换算法的过程中，我还遇到了更多问题，比如在像'或 i = 1 到 k'这样的行中，转换成Python时出现了错误，提示“TypeError: 'int' object is not iterable”（类型错误：'int'对象不可迭代）。

Answer 1

你可以用一个列表的列表来创建你需要的表格：

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' 

关于你的类型错误(TypeError)，你不能写成 i = 1 到 k，而是应该这样写：for i in range(1,k+1):（假设你想包含k）。

还有一个小建议，就是不要把sum当作变量名，因为这已经是Python内置的一个函数了。试着在你的程序里加上print sum([10,4])看看效果！

Answer 2

你可以通过这个代码块来获取创建动态编程表格的部分：

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