我有三个列表，每个列表都有几个可能的值。
probs = ([0.1,0.1,0.2], \
[0.7,0.9], \
[0.5,0.4,0.1])
我想测试从每个列表中选择一个元素的所有可能组合。因此，本例中有 3*2*3=18 种可能的组合。最后，我想根据一些标准选择最有利的组合。这是:
[<index in row 0> , <index in row 1> , <index in row 2> , <criteria value>]
我可以通过使用三个嵌套的 for 循环(我这样做了)来完成我的任务。然而，在这段代码的实际应用中，我会有可变数量的列表。因此，解决方案似乎是使用内部带有 for 循环的递归函数(我也这样做了)。代码:
# three rows. Test all combinations of one element from each row
# This is [value form row0, value from row1, value from row2]
# So: 3*2*3 = 18 possible combinations
probs = ([0.1,0.1,0.2], \
[0.7,0.9], \
[0.5,0.4,0.1])
meu = [] # The list that will store the best combinations in the recursion
#######################################################
def main():
choice = [] #the list that will store the best comb in the nested for
# accomplish by nested for loops
for n0 in range(len(probs[0])):
for n1 in range(len(probs[1])):
for n2 in range(len(probs[2])):
w = probs[0][n0] * probs[1][n1] * probs[2][n2]
cmb = [n0,n1,n2,w]
if len(choice) == 0:
choice.append(cmb)
elif len(choice) < 5:
for i in range(len(choice)+1):
if i == len(choice):
choice.append(cmb)
break
if w < choice[i][3]:
choice.insert(i,cmb)
break
else:
for i in range(len(choice)):
if w < choice[i][3]:
choice.insert(i,cmb)
del choice[-1]
break
# using recursive function
combinations(0,[])
#both results
print('By loops:')
print(choice)
print('By recursion:')
print(meu)
#######################################################
def combinations(step,cmb):
# Why does 'meu' needs to be global
if step < len(probs):
for i in range(len(probs[step])):
cmb = cmb[0:step] # I guess this is the same problem I dont understand recursion
# But, unlike 'meu', here I could use this workaround
cmb.append(i)
combinations(step+1,cmb)
else:
w = 1
for n in range(len(cmb)):
w *= probs[n][cmb[n]]
cmb.append(w)
if len(meu) == 0:
meu.append(cmb)
elif len(meu) < 5:
for i in range(len(meu)+1):
if i == len(meu):
meu.append(cmb)
break
if w < meu[i][-1]:
meu.insert(i,cmb)
break
else:
for i in range(len(meu)):
if w < meu[i][-1]:
meu.insert(i,cmb)
del meu[-1]
break
return
######################################################
main()
它输出，如我所愿:
By loops:
[[0, 0, 2, 0.006999999999999999], [1, 0, 2, 0.006999999999999999], [0, 1, 2, 0.009000000000000001], [1, 1, 2, 0.009000000000000001], [2, 0, 2, 0.013999999999999999]]
By recursion:
[[0, 0, 2, 0.006999999999999999], [1, 0, 2, 0.006999999999999999], [0, 1, 2, 0.009000000000000001], [1, 1, 2, 0.009000000000000001], [2, 0, 2, 0.013999999999999999]]
最初，我想将“meu”列表用作函数的内部，因为我认为最好避免使用全局变量(也许不是……我是新手)。问题是我无法想出一个代码来在深度之间传递“meu”和“cmb”以提供与嵌套循环相同的效果。
如何使用内部“meu”而不是全局列表来实现递归函数？我从递归概念中遗漏了什么？谢谢。
++++++++++++++++++++++++++++++++++++
失败函数示例:
def combinations(choice,step,cmb):
if step < len(probs):
for i in range(len(probs[step])):
cmb = cmb[0:step] #workaroud for cmb
cmb.append(i)
choice = combinations(choice,step+1,cmb)
else:
w = 1
for n in range(len(cmb)):
w *= probs[n][cmb[n]]
cmb.append(w)
if len(choice) == 0:
choice.append(cmb)
elif len(choice) < 5:
for i in range(len(choice)+1):
if i == len(choice):
choice.append(cmb)
break
if w < choice[i][-1]:
choice.insert(i,cmb)
break
else:
for i in range(len(choice)):
if w < choice[i][-1]:
choice.insert(i,cmb)
del choice[-1]
break
return choice
调用者:
choice = combinations([],0,[])
请您参考如下方法:
不要重新发明轮子(无论是否递归):使用随附的电池。您试图解决的问题非常普遍，因此 Python 的标准库中包含一个解决方案。
您想要的——来自一定数量列表的每个值的每个组合——被称为这些列表的笛卡尔积。 itertools.product 的存在是为了为您生成这些内容。
import itertools
probs = ([0.1, 0.1, 0.2],
[0.7, 0.9],
[0.5, 0.4, 0.1])
for prob in itertools.product(*probs):
print prob
# prob is a tuple containing one combination of the variables
# from each of the input lists, do with it what you will
如果您想知道每个项目来自哪个索引，最简单的方法是将索引而不是值传递给 product()。您可以使用 range() 轻松获得它。
for indices in itertools.product(*(range(len(p)) for p in probs)):
# get the values corresponding to the indices
prob = [probs[x][indices[x]] for x in range(len(probs))]
print indices, prob
或者您可以使用 enumerate() —— 这样，产品中的每个项目都是一个包含其索引和值的元组(而不是您在上述方法中获取它们的方式的两个单独列表):
for item in itertools.product(*(enumerate(p) for p in probs)):
print item
