Python列表增加了额外的嵌套

我试图解决类似问题的一个这里列出：Python: Combinations of parent-child hierarchy Python列表增加了额外的嵌套

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

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

来源

2017-01-24 atm

@ TigerhawkT3这是不一样的问题！即使你将'test = find_all_paths（graph，'top'）'修改为'test = find_all_paths（graph，'top'，[]）'，你也会得到相同的问题 – alfasin

这与这个无关作为参数的默认参数在函数的范围内没有因第一次赋值而发生变化。我投票重新提出这个问题。 – 2ps

是的，我会重新打开它。我认为TigerhawkT3在这里有点鲁莽。 – wim

的问题是path之间的混淆是一个单独的列表，并paths，这是一个列表的列表。你的函数可以返回任一个，这取决于你在图中的位置。

您可能想要在所有情况下返回路径列表。因此，在基本情况下将return path更改为return [path]。

在递归的情况下，您现在需要处理合并每个孩子的路径。我建议使用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

来源

2017-01-24 05:08:54 Blckknght

比我提供的更好的解释。 +1 – 2ps

@Andrew：呃，是的，这是一个错字。我编辑过它。对于那个很抱歉。我想这是具有非常相似名称变量的危险的一个很好的例子。 – Blckknght

以下应解决您的问题：

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

来源

2017-01-24 05:05:34 2ps

这里有一个非递归解决方案。但是，它通过排序输出列表来“欺骗”。

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

来源

2017-01-24 06:08:01

Python列表增加了额外的嵌套

回答

相关问题