python - 从嵌套列表列表返回到叶节点的路径列表

Question

我有一个动态树结构，它表示为列表的列表 - 这是一个这样的示例，用空格布局来说明结构:

[['first',     
               [0, 'list1'], 
               [1, 'list2'], 
               [2, 'list3']],
 ['second',    
               ['second_subda', 
                      [0, 'tup1'], 
                      [1, 'tup2']],
               ['second_subdb', 
                      [0, 'tup3'], 
                      [1, 'tup4']]],
 ['third',
               ['third_subda',   
                      [0, 'a'],
                      [1, 'b'],
                      [2, 'c'],
                      [3, 
                            ['d',  
                                  [0, 'e'], 
                                  [1, 'f'], 
                                  [2, 
                                        ['g', 
                                               [0, 1], 
                                               [1, 2], 
                                               [2, 3]]]]]]]]

我想从中提取所有叶节点，以及到达它们所需的路径:

例如从上面的结构来看，我想返回:

[ ( 'list1', ['first', 0 ] ) , 
  ( 'list2', ['first', 1 ] ) , 
  ( 'list3', ['first', 2 ] ) , 
  ( 'tup1' , ['second',  'second_subda', 0 ] ) ,
  ( 'tup2' , ['second',  'second_subda', 1 ] ) ,
  ( 'tup3' , ['second',  'second_subdb', 0 ] ) ,
  ( 'tup4' , ['second',  'second_subdb', 1 ] ) ,
  ( 'a'    , ['third',   'third_subda',  0 ] ) ,  
  ( 'b'    , ['third',   'third_subda',  1 ] ) ,  
  ( 'c'    , ['third',   'third_subda',  2 ] ) ,  
  ( 'e'    , ['third',   'third_subda',  3  , 'd',  0 ] ) ,  
  ( 'f'    , ['third',   'third_subda',  3  , 'd',  1 ] ) ,  
  (  1     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 0 ] ) ,  
  (  2     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 1 ] ) ,  
  (  3     , ['third',   'third_subda',  3  , 'd',  2 , 'g' , 2 ] )]

即对于每个“叶子”，我想提取一个由所有叶子值组成的元组，以及描述到达该叶子项目的唯一路径的所有初始列表条目的列表。我应该留下这些元组的列表，其中列表中的项目数对应于树中的叶节点数。

我尝试在像 networkx 这样的模块中构建这棵树，但是附加模块的开销对于我的用例来说是过度的。我只是想尽可能坚持使用普通的 python 代码。

Answer 1

您可以使用带有生成器的递归:

data = [['first', [0, 'list1'], [1, 'list2'], [2, 'list3']], ['second', ['second_subda', [0, 'tup1'], [1, 'tup2']], ['second_subdb', [0, 'tup3'], [1, 'tup4']]], ['third', ['third_subda', [0, 'a'], [1, 'b'], [2, 'c'], [3, ['d', [0, 'e'], [1, 'f'], [2, ['g', [0, 1], [1, 2], [2, 3]]]]]]]]
def get_paths(d, c = []):
  for a, *b in d:
    if len(b) == 1 and not isinstance(b[0], list):
      yield (b[0], c+[a])
    else:
      yield from get_paths(b, c+[a])

print(list(get_paths(data)))

输出:

[('list1', ['first', 0]), 
 ('list2', ['first', 1]), 
 ('list3', ['first', 2]), 
 ('tup1', ['second', 'second_subda', 0]), 
 ('tup2', ['second', 'second_subda', 1]), 
 ('tup3', ['second', 'second_subdb', 0]), 
 ('tup4', ['second', 'second_subdb', 1]), 
 ('a', ['third', 'third_subda', 0]), 
 ('b', ['third', 'third_subda', 1]), 
 ('c', ['third', 'third_subda', 2]), 
 ('e', ['third', 'third_subda', 3, 'd', 0]), 
 ('f', ['third', 'third_subda', 3, 'd', 1]), 
 (1, ['third', 'third_subda', 3, 'd', 2, 'g', 0]), 
 (2, ['third', 'third_subda', 3, 'd', 2, 'g', 1]), 
 (3, ['third', 'third_subda', 3, 'd', 2, 'g', 2])]