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

Question

我的问题很难解释：

首先，这里有一些背景：

假设有一个 3*6 table 的空间，里面有一些物品（假设是 4 个）。这些项目可以根据特定规则在此 table 中移动。我想获得这些项目的所有可能位置。我的解决方案是为每个项目计算出一个"movement space"，其中一个项目可以在不违反规则的情况下自由移动，然后生成所有可能的放置。

一件重要的事情：一个项目的 "movement space" 取决于其他项目的位置。如果一个项目改变了它的位置，其他项目的 "movement space" 也会改变。

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

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

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

我们有一个函数可以计算给定字典中给定项目的 "movement space"。

available_pos('a', position_dict)

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

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

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

这会更新 1 个项目的位置，因此下一步是让它更新多个项目的位置。因此，我们不会传递单个项目，而是传递一个项目列表。

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

现在剩下要做的就是实际产生一个结果：

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

我没有测试这段代码，但它至少应该让你知道如何解决你的问题。

Answer 2

这也许

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

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

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

python

recursion

for-loop

nested-loops