嵌套for循环到Python中的递归函数

Question

我有三个列表,每个列表都有几个可能的值.

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,[])

Answer 1

不要重新发明轮子(递归或不重复):使用附带的电池.您尝试解决的问题非常普遍,因此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