递归 - 在Python中创建n层嵌套的“for”循环

Question

我的问题难以解释：

首先，这里有一些背景信息：

想象一下有一个3*6的表格，里面有一些物品（比如说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开始，而且更糟的是，坐标中的第一个数字是列，第二个数字是行。我做了一些琐碎的事情，但如果我改回去，问题仍然存在。

- Han Zhang

---

你想要先放置它们还是放置后再移动它们？如果你只想放置它们，那么这就是一个相当基础的计算机科学问题。 - Elmex80s

@Elmex80s 我想先放置它们，然后再移动它们。每个项目在表格中都有一个初始位置，确定了它们的初始“移动空间”。但是，当一个项目移动到另一个位置时，其他项目的移动空间可能会改变。 - Han Zhang

项目的初始位置是如何确定的？表格除了它们之外是否为空？ - martineau

@martineau 其他地方都是空的！规则实际上非常简单！一个物品应该被限制在一个矩形内，其中左右不应超过最近的占用单元格（仅考虑x轴，无论它们的y轴如何）。同样，上下不应超过y轴上最近的占用单元格！当然，如果这个矩形中已经有占用的单元格，它们将被移除。我希望我描述得很清楚... - Han Zhang

你的索引没有意义。对于一个 3x6 的表格，第一个索引应该在 0 到 2 范围内，第二个索引应该在 0 到 5 范围内，然而你在 position_dict 中的位置 (1,6) 上放置了 'a'。假设你想表示的是位置 (0,5)，那么周围只有 3 个空位置可用：[(1,5), (0,4), (1,4)]，而不是你在问题中提到的 5 个。请澄清并相应地[编辑]你的问题。 - martineau

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

- Elmex80s

Answer 2

递归是这里的解决方法。由于您正在多次执行相同的操作，编写一个函数来执行它是很自然的。

让我们从一个非递归函数开始。它可能看起来像这样：

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

我没有测试过这段代码，但它至少应该给你一个解决问题的思路。

- Aran-Fey