CODEWITHSUNDEEP
pythonrecursionnested-loops
fdireito
fdireito

Reputation: 1729

Nested for loops to recursive function in Python

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

Upvotes: 1

Views: 1657

Answers (1)

kindall
kindall

Reputation: 184101

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

Upvotes: 5

Related Questions