Python递归函数从特定类型的字典生成特定类型的序列

Question

我需要编写一个算法，其中有一个Python字典，例如{1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4 : [5, 7]} 并生成 [[1, 2, 3, 4, 5,8],[1, 2, 3, 4, 5,9], [1,2,3,4, 7], [1, 6, 5,8], [1, 6, 5,9]]。

这里基本上将从字典的第一个元素开始并将值附加到键上。它应该创建 n 个列表，其中 n 是值列表的大小。例如。在第一个循环中，创建了 2 个列表 [1,2] 和 [1,6]，此外，它应该检查任何列表的最后一个值是否是键值，它应该将其值附加到该特定列表。这里，由于 2 是第一个列表的最后一个值，因此它将附加 [1,2,3]，列表为 [1,2,3] 和 [1,6]。此外，在 dict 的下一次迭代中，列表将更新为 [1,2,3] 和 [1,6, 5] 等。希望你明白了，最后应该以上面的列表结束。

我的解决方案： 列表=[] 行 = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [], 4: [5,7]}

def create_lines(cont=False):
    for k,val in lines.items():
        print(lists)
        for l in lists:
            if k==l[-1]:
                if lines[k]:
                    l.append(lines[k][0])
                    cont=True
                    break
        if cont:               
            continue

        for v in val:
            lists.append(list([k,v]))
            cont=False
    for l in lists:
        print("second loop")
        if l[-1] in lines and lines[l[-1]]:
            create_lines()
    
create_lines()

进入无限循环

来自聊天GPT：

def all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.get(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            new_paths = all_paths(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

# Given dictionary
graph_dict = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}

# Define the start and end points
start_point = 1
end_point = 8

# Find all possible paths
paths = all_paths(graph_dict, start_point, end_point)

# Filter paths that do not end with the end point
valid_paths = [p for p in paths if p[-1] == end_point]

# Print the valid paths
print(valid_paths)

结果： [[1,2,3,4,5,8],[1,6,5,8]]

Answer 1

尝试：

dct = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}


def get_lists(d, start):
    if start[-1] not in d:
        yield start
        return

    for v in d[start[-1]]:
        yield from get_lists(d, start + [v])


print(list(get_lists(dct, [1])))

打印：

[
 [1, 2, 3, 4, 5, 8], 
 [1, 2, 3, 4, 5, 9], 
 [1, 2, 3, 4, 7], 
 [1, 6, 5, 8], 
 [1, 6, 5, 9]
]