Nested for loops to recursive function in Python
Question: I have three lists, each one with several possible values.

    
    
    probs = ([0.1,0.1,0.2], \
             [0.7,0.9], \
             [0.5,0.4,0.1])
    

I want to test all possible combinations of choosing one element from each
list. So, 3*2*3=18 possible combinations in this example. In the end, I want
to choose the most favourable combinations according to some criteria. This
is:

    
    
    [<index in row 0> , <index in row 1> , <index in row 2> , <criteria value>]
    

I can accomplish my task by using three nested for loops (which I did).
However, in the real application of this code, I will have a variable number
of lists. Because of that, it seems the solution would be using a recursive
function with a for loop inside it (which I did as well). The code:

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

It outputs, as I wanted:

    
    
    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]]
    

Initially, I wanted to use the 'meu' list as internal of the function,
because, I thought, it would be better to avoid global variables (perhaps
not... I'm a newbie). The problem was I could not come up with a code that
would pass both 'meu' and 'cmb' between depths to give the same effect of the
nested loops.

How could I implement a recursive function with internal 'meu' instead of
being a global list? What am I missing from recursion concept? Thanks.

++++++++++++++++++++++++++++++++++

Example of a failed function:

    
    
    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
    

Called by:

    
    
    choice = combinations([],0,[])
    


Answer: Don't reinvent the wheel (recursively or not): use the included batteries. The
problem you are trying to solve is extremely common and so a solution is
included in Python's standard library.

What you want—every combination of every value from some number of lists—is
called the Cartesian product of those lists. `itertools.product` exists to
generate those for you.

    
    
    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
    

If you want to know what index each item comes from, the easiest way is to
just pass the indices to `product()` rather than the values. You can easily
get that using `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
    

Or you could use `enumerate()` \-- this way, each item in the product is a
tuple containing its index and its values (not two separate lists the way you
get them in the above method):

    
    
     for item in itertools.product(*(enumerate(p) for p in probs)):
         print item
    

