python - 递归 - 在 Python 中创建 n 嵌套 "for"循环

Question

我的问题很难解释:

首先，这里有一些背景:

假设有一个 3*6 的 table ，里面有一些元素(假设是 4 个)。这些项目可以根据特定规则在此表中移动。我想获得这些项目的所有可能位置。我的解决方案是为每个元素找出一个“移动空间”，一个元素可以在不违反规则的情况下自由移动，然后生成所有可能的放置。

一件重要的事情:一个项目的“移动空间”取决于其他项目的位置。如果一个项目改变了它的位置，其他项目的“移动空间”也会改变。

假设我们有四个项目，它们的初始位置存储在字典中:

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

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

我们有一个函数可以计算给定字典中给定项目的“移动空间”。

available_pos('a', position_dict)

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

好的，问题来了。我正在编写一个丑陋的嵌套“for”循环来生成展示位置。它首先更新字典并获取下一项的移动空间，然后循环这个新的移动空间。直到达到最低水平。

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

这是有问题的，因为我有 500 多个类似的问题，每个案例都有不同数量的项目和位置设置。因此，我想知道是否可以创建一个n嵌套循环的函数，可以在每一层创建一个新的待迭代字典？

我知道递归可以解决问题，但我对它不是很熟悉。有什么建议吗？

谢谢!

编辑:

索引系统对你来说可能看起来很奇怪，因为它从 1 开始，更糟糕的是，坐标中的第一个数字指的是列，第二个数字指的是行。我这样做是出于一些微不足道的原因，但如果我将它们改回来，问题仍然存在。

Answer 1

这可能是

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)

您调用 do_step('a', position_dict.copy(), 10)。 position_dict 已给出。

这是非功能性版本，应该运行得更快

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