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

Question

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.

Answer 1

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