CODEWITHSUNDEEP
pythonfor-looprecursionnested-loops
Han Zhang
Han Zhang

Reputation: 65

recursion - Creating n-nested "for" loops in Python

My problem is difficult to explain:

First, here are some backgrounds:

Imagine there is a 3*6 table with some items in it (let's say 4). These items can be moved around in this table, based on certain rules. I want to get all possible placements of these items. My solution is to figure out a "movement space" for each item, where an item can move freely without violating the rules, and then generate all possible placements.

One important thing: an item's "movement space" depends on other items' positions. If one item changes its position, the "movement space" for other items can change, too.

Let's say we have four items and their initial position is stored in a dictionary:

items = ['a','b','c','d']

position_dict = {'a': (1, 6), 'b': (1, 1), 'c': (1, 4), 'd': (2, 1)}

We have a function for figuring out the "movement space" for a given item in a given dictionary. 

available_pos('a', position_dict)

[(1, 5), (1, 6), (2, 4), (2, 5), (2, 6)]

OK, here is the problem. I'm writing an ugly nested 'for' loops to generate the placements. It first updates the dict and gets the movement space for the next item, and then loop this new movement space. until it reaches the lowest level. 

pos = []

ava1 = available_pos('a', position_dict) # a dict for a's space

for a in ava1:
    position_dict['a'] = a # update the dict
    ava2 = available_pos('b', position_dict) # new dict for b's space

    for b in ava2:
        position_dict['b'] = b # update the dict
        ava3 = available_pos('c', position_dict) # new dict for c's space

        for c in ava3:
            position_dict['c'] = c # update the dict
            ava4 = available_pos('d', position_dict) # new dict for d's space

            for d in ava4:
                pos.append([a, b, c, d])

This is problematic because I have 500+ same problems like this with each case having a different number of items and location setting. Therefore, I would like to know if it is possible to create a function for n-nested loops that can create a new to-be-iterated dict at each level?

I know recursion may do the trick but I am not very familiar with it. Any suggestions?

Thank you!

EDIT:

The index system might seem strange to you because it starts from 1, and even worse, the first number in the coordinate refers to the column and the second number refers to the row. I did this for some trivial reasons but the problem still holds if I change them back.

Upvotes: 3

Views: 5131

Answers (2)

Elmex80s
Elmex80s

Reputation: 3504

This maybe

def do_step(item, position_dict, depth):
    print position_dict

    if depth > 0:           
        new_positions = available_pos(item, position_dict)

        for (x, y) in new_positions:
            position_dict[item] = (x, y)

            for next_item in ['a', 'b', 'c', 'd']:
                do_step(next_item, position_dict.copy(), depth - 1)

You call do_step('a', position_dict.copy(), 10). position_dict was given.

This is the non-functional version which should run faster 

def do_step(item, position_dict, depth):
    print position_dict

    if depth > 0:   
        old_position = position_dict[item]        
        new_positions = available_pos(item, position_dict)

        for (x, y) in new_positions:
            position_dict[item] = (x, y)

            for next_item in ['a', 'b', 'c', 'd']:
                do_step(next_item, position_dict, depth - 1)

        # Restore the old position  
        position_dict[item] = old_position

Upvotes: 1

Aran-Fey
Aran-Fey

Reputation: 43166

Recursion is the way to go here. Since you're doing the same thing multiple times, it's only natural to write a function to do it.

Let's start with a non-recursive function. It could look like this:

def update_pos(item):
    ava1 = available_pos(item, position_dict)

    for a in ava1:
        position_dict[item] = a
        # but now what? we need to update the next item's location

This updates 1 item's position, so the next step is to make it update multiple items' positions. So instead of passing a single item, we'll pass it a list of items.

def update_pos(items_): # I called it items_ to avoid a name clash with the global items list
    item= items_[0]
    ava1 = available_pos(item, position_dict)

    for a in ava1:
        position_dict[item] = a
        #recursively update the remaining items' positions
        if len(items_) > 1:
            update_pos(items_[1:])

All that's left to do now is to actually produce a result:

def update_pos(items_):
    item= items_[0]
    ava1 = available_pos(item, position_dict)

    for a in ava1:
        position_dict[item] = a
        #recursively update the remaining items' positions
        if len(items_) > 1:
            update_pos(items_[1:])
        else:
            pos.append([position_dict[i] for i in items])

I didn't test this code, but it should at least give you an idea how to solve your problem.

Upvotes: 0

Related Questions