时间戳

首页 > 解决方案 > Python中的递归，从每个循环中创建几个新实例

python - Python中的递归，从每个循环中创建几个新实例

问题描述

我有一个问题，我有一个包含类对象的字典，它引用一个或多个项目。字典的键是每个项目的 id。我正在尝试为 x 步设置一个递归函数来查找相邻项目 ID 的链。

它有效，但前提是每个“adjacent_items”变量中只有一个项目。如果还有更多，它仍然只抓住第一个并继续前进。在示例中，从未处理过“7”。

我对递归函数很陌生，但我觉得应该有一种有效的方法，所以用递归解决这个问题。任何输入将不胜感激。

class Item:
    def __init__(self, id_num: str, adjacent: list):
        self.id = id_num
        self.adjacent_items = adjacent


def get_adjacent_x_steps(start: str, item_dict: dict, x: int, wip_set=None):
    """Get adjacent items for x steps"""

    if wip_set is None:
        wip_set = set()
    if x != 0:
        x -= 1
        for item in item_dict[start].adjacent_items:
            wip_set.add(item)
            # Todo, only takes first hit, return exits this instance..
            return get_adjacent_x_steps(item, item_dict, x, wip_set)
    else:
        return wip_set


def example():
    """Example items"""
    item1 = Item("1", ["4", "7"])
    item2 = Item("4", ["5"])
    item3 = Item("7", ["5"])
    item4 = Item("5", ["8", "17"])

    item_dict = {}
    for item in (item1, item2, item3, item4):
        item_dict[item.id] = item

    chained_items = get_adjacent_x_steps("1", item_dict, 2)

    print(chained_items)


if __name__ == '__main__':
    example()

标签： pythonrecursion

解决方案

尝试以下操作：

class Item:
    def __init__(self, id_num: str, adjacent: list):
        self.id = id_num
        self.adjacent_items = adjacent

def get_adjacent_x_steps(start, item_dict, x):
    if x == 0 or start not in item_dict:
        return [[]]
    return [[adj, *lst]
            for adj in item_dict[start].adjacent_items
            for lst in get_adjacent_x_steps(adj, item_dict, x - 1)]

item1 = Item("1", ["4", "7"])
item2 = Item("4", ["5"])
item3 = Item("7", ["5"])
item4 = Item("5", ["8", "17"])
item_dict = {i.id: i for i in (item1, item2, item3, item4)}

print(get_adjacent_x_steps('1', item_dict, 1))
print(get_adjacent_x_steps('1', item_dict, 2))
print(get_adjacent_x_steps('1', item_dict, 3))

递归发生在列表理解中；at start，获取所有相邻的项目（for adj in item_dict[start].adjacent_items），并将该函数应用于那些少一步的项目（get_adjacent_x_steps(adj, item_dict, x - 1)）。然后将结果列表lst与adj.

输出：

[['4'], ['7']]
[['4', '5'], ['7', '5']]
[['4', '5', '8'], ['4', '5', '17'], ['7', '5', '8'], ['7', '5', '17']]

如果您想获得一组目的地，那么您可以在之后应用一组理解：

print({x[-1] for x in get_adjacent_x_steps('1', item_dict, 3)})
# {'17', '8'}

推荐阅读