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.

Do you want to place them or place them first and after placing them you want to move them? If you only want to place them then this is a rather basic computer science problem I think. — Elmex80s
– Elmex80s, Commented Feb 23, 2017 at 19:42
@Elmex80s I think I want to place them and then move them. Each item has an initial position in the table, which determines their initial "movement space". But, as one item moves to another position, other items' movement space may change. — Han Zhang
– Han Zhang, Commented Feb 23, 2017 at 20:01
Does it matter which one moves first? Or do they 'try' to move at the same time, that is at each iteration 'a', 'b', 'c' and 'd' move to their new position? — Elmex80s
– Elmex80s, Commented Feb 23, 2017 at 20:06
How is the initial position of the items determined and does the table start out empty except for them? — martineau
– martineau, Commented Feb 23, 2017 at 20:08
@martineau The other places are empty! The rules are actually pretty simple! An item should be limited in a rectangle where left and right should not exceed the nearest occupied cells (only consider x- axis, regardless of their y-axis). Similarly, up and down should not exceed the nearest occupied cells on y-axis! And of course if there are already occupied cells in this rect they are removed. I hope I described it clearly... — Han Zhang
– Han Zhang, Commented Feb 23, 2017 at 20:32

Elmex80s · Accepted Answer · 2017-02-24 20:09:24Z

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

Aran-Fey · Accepted Answer · 2017-02-23 20:09:04Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related