Python list of lists 递归增加了额外的嵌套

Question

我正在尝试解决与此处列出的问题类似的问题：Python: Combinations of parent-child hierarchy

graph = {}

nodes = [
('top','1a'),
('top','1a1'),
('top','1b'),
('top','1c'),
('1a','2a'),
('1b','2b'),
('1c','2c'),
('2a','3a'),
('2c','3c'),
('3c','4c')
]

for parent,child in nodes:
    graph.setdefault(parent,[]).append(child)

def find_all_paths(graph, start, path=[]):
    path = path + [start]

    if not graph.has_key(start):
        return path

    paths = []

    for node in graph[start]:
        paths.append(find_all_paths(graph, node, path))

    return paths

test = find_all_paths(graph, 'top')

期望的输出：

[['top', '1a', '2a', '3a'],
 ['top', '1a1'],
 ['top', '1b', '2b'],
 ['top', '1c', '2c', '3c', '4c']]

实际输出：

[[[['top', '1a', '2a', '3a']]],
 ['top', '1a1'],
 [['top', '1b', '2b']],
 [[[['top', '1c', '2c', '3c', '4c']]]]]

关于如何删除额外嵌套的任何建议？谢谢！

Answer 1

以下应该可以解决您的问题：

 def find_all_paths(graph, start, path=None):
    if path is None: 
        # best practice, avoid using [] or {} as
        # default parameters as @TigerhawkT3 
        # pointed out.
        path = []
    path = path + [start]

    if not graph.has_key(start):
        return [path] # return the path as a list of lists!

    paths = []
    for node in graph[start]:
        # And now use `extend` to make sure your response
        # also ends up as a list of lists
        paths.extend(find_all_paths(graph, node, path))

    return paths

Answer 2

问题是 path（单个列表）和 paths（列表的列表）之间的混淆。您的函数可以 return 任意一个，具体取决于您在图表中的位置。

您可能想要 return 所有情况下的路径列表。因此，将基本案例中的 return path 更改为 return [path].

在递归情况下，您现在需要处理将每个 child 的路径合并在一起的问题。我建议使用 paths.extend(...) 而不是 paths.append(...).

将所有这些放在一起，您会得到：

def find_all_paths(graph, start, path=[]):
    path = path + [start]

    if not graph.has_key(start):
        return [path]

    paths = []

    for node in graph[start]:
        paths.extend(find_all_paths(graph, node, path))

    return paths

Answer 3

这是一个 non-recursive 解决方案。但是，它 "cheats" 通过对输出列表进行排序。

def find_all_paths(edges):
    graph = {}
    for u, v in edges:
        if u in graph:
            graph[v] = graph[u] + [v]
            del graph[u]
        else:
            graph[v] = [u, v]
    return sorted(graph.values())

data = (
    ('top','1a'),
    ('top','1a1'),
    ('top','1b'),
    ('top','1c'),
    ('1a','2a'),
    ('1b','2b'),
    ('1c','2c'),
    ('2a','3a'),
    ('2c','3c'),
    ('3c','4c'),
)

test = find_all_paths(data)
for row in test:
    print(row)

输出

['top', '1a', '2a', '3a']                                                                                                                      
['top', '1a1']                                                                                                                                 
['top', '1b', '2b']                                                                                                                            
['top', '1c', '2c', '3c', '4c']

Python list of lists 递归增加了额外的嵌套

Python list of lists recursion adds extra nesting

python

recursion

nested-lists